Merge Sort a Linked List

typedef struct _aList {
    struct _aList* next;
    struct _aList* prev; // Optional.
       // some data
} aList;

aList *merge_sort_list(aList *list,int (*compare)(aList *one,aList *two))
{
    int listSize=1,numMerges,leftSize,rightSize;
    aList *tail,*left,*right,*next;
    if (!list || !list->next) return list;  // Trivial case

    do { // For each power of two<=list length
        numMerges=0,left=list;tail=list=0; // Start at the start

        while (left) { // Do this list_len/listSize times:
            numMerges++,right=left,leftSize=0,rightSize=listSize;
            // Cut list into two halves (but don't overrun)
            while (right && leftSize<listSize) leftSize++,right=right->next;
            // Run through the lists appending onto what we have so far.
            while (leftSize>0 || (rightSize>0 && right)) {
                // Left empty, take right OR Right empty, take left, OR compare.
                if (!leftSize)                  {next=right;right=right->next;rightSize--;}
                else if (!rightSize || !right)  {next=left;left=left->next;leftSize--;}
                else if (compare(left,right)<0) {next=left;left=left->next;leftSize--;}
                else                            {next=right;right=right->next;rightSize--;}
                // Update pointers to keep track of where we are:
                if (tail) tail->next=next;  else list=next;
                // Sort prev pointer
                next->prev=tail; // Optional.
                tail=next;
            }
            // Right is now AFTER the list we just sorted, so start the next sort there.
            left=right;
        }
        // Terminate the list, double the list-sort size.
        tail->next=0,listSize<<=1;
    } while (numMerges>1); // If we only did one merge, then we just sorted the whole list.
    return list;
}

typedef struct _aList {
    struct _aList* next;
    struct _aList* prev; // Optional.
       // some data
} aList;

aList* merge_sort_list_recursive(aList *list,int (*compare)(aList *one,aList *two))
{
    if (!list || !list->next) return list;  // Trivial case.
    aList *right=list,*temp=list,*last=list,*result=0,*next=0,*tail=0;
    // Find halfway through the list (by running two pointers, one at twice the speed of the other).
    while (temp && temp->next) {last=right;right=right->next,temp=temp->next->next;}
    last->next=0;   // Break the list in two. (prev pointers are broken here, but we fix later)
    // Recurse on the two smaller lists:
    list=merge_sort_list_recursive(list,compare);
    right=merge_sort_list_recursive(right,compare);
    // Merge:
    while (list || right)
    {
        // Take from empty lists, or compare:
        if (!right)                     {next=list;list=list->next;}
        else if (!list)                 {next=right;right=right->next;}
        else if (compare(list,right)<0) {next=list;list=list->next;}
        else                            {next=right;right=right->next;}
        if (!result) result=next; else tail->next=next;
        next->prev=tail;    // Optional.
        tail=next;
    }
    return result;
}

public int[] msort(int[] a) {
    if (a.Length > 1) {
        int min = a.Length / 2;
        int max = min;

        int[] b = new int[min];
        int[] c = new int[max]; // dividing main array into two half arrays
        for (int i = 0; i < min; i++) {
            b[i] = a[i];
        }

        for (int i = min; i < min + max; i++) {
            c[i - min] = a[i];
        }

        b = msort(b);
        c = msort(c);

        int x = 0;
        int y = 0;
        int z = 0;

        while (b.Length != y && c.Length != z) {
            if (b[y] < c[z]) {
                a[x] = b[y];
                //r--
                x++;
                y++;
            } else {
                a[x] = c[z];
                x++;
                z++;
            }
        }

        while (b.Length != y) {
            a[x] = b[y];
            x++;
            y++;
        }

        while (c.Length != z) {
            a[x] = c[z];
            x++;
            z++;
        }
    }

    return a;
}

struct node {
   int data1;
   int data2;
   struct node *next;
};