Sort list using merge sort

After heapsort implementation for linked list, I tried merge sort. Merge sort is suitable implementation for sorting linked lists.

Merge sort includes dividing the list and merging lists. The recursive implementation of merge sort includes keep dividing the input till list/array includes only one element.

Merge sort implementation for arrays needs extra array space as it has to access input and copy in order. In case of linked list, just frame a new list with existing lists nodes, no extra space required.

This merge sort can be implemented in two ways : recursive approach, iterative approach.

Below is the recursive approach. For dividing the list , I used slow, fast pointers:

struct ListNode * mergel(struct ListNode *l1, struct ListNode *l2){
    struct ListNode *rs = NULL, *tr=NULL;
    
    if (l1->val < l2->val){
        rs = l1; l1=l1->next; tr = rs;
    }else {
        rs=l2; l2=l2->next; tr = rs;
    }
    
    while (l1 && l2){
        if (l1->val < l2->val){
            tr->next = l1; l1=l1->next;
        }else{
            tr->next =l2; l2=l2->next;
        }
        tr= tr->next;
    }
    while(l1){
        tr->next = l1; l1=l1->next;
        tr= tr->next;
    }
    while(l2){
        tr->next = l2; l2=l2->next;
        tr= tr->next;
    }
    return rs;
}

struct ListNode *mergesortl(struct ListNode *hd){
    if (!hd || !(hd->next))
        return hd;
    struct ListNode *tmp = hd, *f= hd->next;
    
    while(tmp && f && f->next){
        tmp = tmp->next;
        f = f->next->next;
    }
    f = tmp->next;
    tmp->next = NULL;
    
    hd = mergesortl(hd);
    f = mergesortl(f);
    hd = mergel(hd, f);
    return hd;
}

Iterative approach:

This is a complex solution .
There are 2 while loops :

• One while loop is to divide the lists of size to 1, 2, 4, 8,..
• another while loop to actually divide the lists and merge. Log N times we are going through the entire list. Challenges here is like joining the lists after merge called, again at the end of loop, the second list may exist or not. This condition also to be taken care of.
  Its complex, theoretically no space complexity, but slower than recursive approach.

Below is the program I tried implementing:

struct ListNode * mergele(struct ListNode *l1, struct ListNode *l2, struct ListNode **pe){
    struct ListNode *rs = NULL, *tr=NULL, *prev= NULL;
    
    if (l1->val < l2->val){
        rs = l1; l1=l1->next; tr = rs;
    }else {
        rs=l2; l2=l2->next; tr = rs;
    }
    
    while (l1 && l2){
        if (l1->val < l2->val){
            tr->next = l1; l1=l1->next;
        }else{
            tr->next =l2; l2=l2->next;
        }
        prev = tr;
        tr= tr->next;
    }
    while(l1){
        tr->next = l1; l1=l1->next;
        prev = tr;
        tr= tr->next;
    }
    while(l2){
        tr->next = l2; l2=l2->next;
        prev = tr;
        tr= tr->next;
    }
    *pe = prev;
    return rs;
}

struct ListNode *imergesortl(struct ListNode *hd){
    if (!hd || !(hd->next))
        return hd;
    struct ListNode *l1,*l2, *l3;
    int size=1, l=0, tot=0;
    struct ListNode *end, *pe, *prev, *tmp;
    
    do {
        tmp= l1=hd;
        hd=NULL; l2= NULL;
        while (tmp->next){
            l++;
            prev=tmp;
            tmp = tmp->next;
            if (!(l%size) && !l2){
                l2= tmp;
                prev->next = NULL;
            }else if ( !(l%(2*size))){
                l3= tmp;
                prev->next=NULL;
                if (!hd){
                    hd = mergele(l1,l2, &end);
                    pe = end;
                }else{
                    pe->next=mergele(l1,l2,&end);
                    pe = end;
                }
                l1= l3; l2 =NULL;
            }
        }
        if (l1 && l2){
            if (!hd)
                hd = mergele(l1,l2,&end);
            else
                pe->next = mergele(l1,l2,&end);
        }else if (l1){
            if (!hd)
                hd = l1;
            else
                hd = mergele(hd,l1,&end);
        }
        if (!tot) tot=l;
        size <<=1;
    }while (size>(tot/2));
    return hd;
}
struct ListNode* sortList(struct ListNode* head){
    return imergesortl(head);
}

Please give your comments.