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

Question

I wrote the following function which counts repeating instances of strings while creating a sorted sequence of strings. However it was slow, then I realized that is O(n^2). So I would like to make it O(n logn) but I don't know how to proceed. Are there any known methods for converting such n^2 algorithm to nlogn? How should one convert it?

void insert (struct listNode **ptr, char *value) {
    struct listNode *newPtr;
    int cmp;

    // find a place to instert node to LL
    while(*ptr){
        // Comparision to detect & remove duplicates nodes

        cmp = strcmp(value, (*ptr)->data);
        // duplicate
        if(cmp == 0){
            (*ptr)->occurrence++;
            return; 
        }
        // the point where i need to add the node
        if(cmp < 0) 
            break;

        ptr = &(*ptr)->next;
    }

    // now here *ptr points to the pointer that i want to change
    // it can be NULL, if we are at the end of the LL

    newPtr = malloc(sizeof *newPtr);
    if(!newPtr)
        return;

    newPtr->data = strdup(value);
    newPtr->occurrence = 1;

    if(newPtr->data == NULL){
        free(newPtr);
        return;     
    }

    // here we are connecting our brand new node to the LL
    newPtr->next = *ptr;
    *ptr = newPtr;
}

struct listNode {
    char *data;
    struct listNode *next;
    int occurrence;
};

Answer 1

Are there any known methods for converting such n² algorithm to n*logn?

In situations when one of the two ns that you multiply comes from accessing a linear data structure, such as your linked list, you can improve to n*logn by moving to a faster data structure, such as a balanced binary tree.

This would translate into replacing the while loop search, which is linear, with a search in a binary tree, which is logn.