MergeSort

For arrays:

1. Top-down:

Any better way to write this code?

 vector<int> aux;
 void merge(vector<int>& a, int lo, int mid, int hi)
 {
       int i = lo, j = mid + 1;
       for (int k = lo; k <= hi; k++)
      {
           aux[k] = a[k];
       }
       for (int k = lo; k <= hi; k++)
       {
             if (i > mid)
              a[k] = aux[j++];
             else if (j > hi)
              a[k] = aux[i++];
             else if (aux[i] > aux[j])
              a[k] = aux[j++];
             else
              a[k] = aux[i++];
       }
 }

 void sort(vector<int> &a, int lo, int hi)
 {
       if (hi <= lo) return;
       int mid = lo + (hi - lo) / 2;
       sort(a, lo, mid);
       sort(a, mid + 1, hi);
       merge(a, lo, mid, hi);
 }

 void mergeSort(vector<int> &a)
 {
       int len = a.size();
       aux = a;
       sort(a, 0, len - 1);
 }

2. Bottom up

void mergesortBU(vector<int> &a, int l, int r)
{ 
        for (int m=l; m<=r-l; m=m+m)
           for (int i=l; i<=r-m; i+=2*m)
                merge(a, i, i+m-1; min(i+2*m-1,r));
}

For singly linked list:
1. Top down:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head==NULL||head->next==NULL) return head;
        ListNode *a=head, *b = head->next;
       
        while(b!=NULL&&b->next!=NULL)
        {
            a=a->next;
            b = b->next->next;
        }
        b=a->next;
        a->next=NULL;
        return merge(sortList(head), sortList(b));
    }
   
    ListNode *merge(ListNode *a, ListNode *b)
    {
        if (a==NULL) return b;
        if (b==NULL) return a;
        ListNode dummy(-1);
        ListNode *cur = &dummy;
       
        while(a!=NULL&&b!=NULL)
        {
            if ( a->val<b->val)
            {
                cur->next = a;
                cur = a;
                a=a->next;
            }
            else
            {
                cur->next = b;
                cur = b;
                b=b->next;
            }
        }
        cur->next = a!=NULL?a:b;
        return dummy.next;
    }
};

2. Bottom up: (Sort a linked list in O(n log n) time using constant space ) Is this constant space?
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head==NULL||head->next==NULL) return head;
       
        queue<ListNode *>  Q;
        for (ListNode *a=NULL; head!=NULL; head=a)
        {
            a = head->next;
            head->next = NULL;
            Q.push(head);
        }
       
        ListNode *t = Q.front();
        Q.pop();
       
        while(!Q.empty())
        {
            Q.push(t);
            t = Q.front();
            Q.pop();
            ListNode *p = Q.front();
            Q.pop();
            t = merge(t,p);
        }
       
        return t;
    }
   
    ListNode *merge(ListNode *a, ListNode *b)
    {
        if (a==NULL) return b;
        if (b==NULL) return a;
        ListNode dummy(-1);
        ListNode *cur = &dummy;
       
        while(a!=NULL&&b!=NULL)
        {
            if ( a->val<b->val)
            {
                cur->next = a;
                cur = a;
                a=a->next;
            }
            else
            {
                cur->next = b;
                cur = b;
                b=b->next;
            }
        }
        cur->next = a!=NULL?a:b;
        return dummy.next;
    }
};