c - How to convert insertion sort to an O(n logn) algorithm? -

c - How to convert insertion sort to an O(n logn) algorithm? -

i wrote next function counts repeating instances of strings while creating sorted sequence of strings. slow, realized o(n^2). create o(n logn) don't know how proceed. there known methods converting such n^2 algorithm nlogn? how should 1 convert it?

void insert (struct listnode **ptr, char *value) { struct listnode *newptr; int cmp; // find place instert node ll while(*ptr){ // comparision observe & remove duplicates nodes cmp = strcmp(value, (*ptr)->data); // duplicate if(cmp == 0){ (*ptr)->occurrence++; return; } // point need add together node if(cmp < 0) break; ptr = &(*ptr)->next; } // here *ptr points pointer want alter // can null, if @ end of ll newptr = malloc(sizeof *newptr); if(!newptr) return; newptr->data = strdup(value); newptr->occurrence = 1; if(newptr->data == null){ free(newptr); return; } // here connecting our brand new node ll newptr->next = *ptr; *ptr = newptr; } struct listnode { char *data; struct listnode *next; int occurrence; };

are there known methods converting such n2 algorithm n*logn?

in situations when 1 of 2 ns multiply comes accessing linear info structure, such linked list, can improve n*logn moving faster info structure, such balanced binary tree.

this translate replacing while loop search, linear, search in binary tree, logn.

c algorithm sorting insertion-sort