Merge Sorted Array

    void merge(int A[], int m, int B[], int n) {
        int pos=m+n-1;
        int i=m-1,j=n-1;
        while(i>=0&&j>=0){
            if(A[i]>B[j]){
                A[pos--]=A[i--];
            }
            else{
                A[pos--]=B[j--];
            }
        }
        while(j>=0)
            A[pos--]=B[j--];
    }

Count Inversions in an array - use merge sort

 观察归并排序——合并数列(1，3，5)与(2，4)的时候：
1．先取出前面数列中的1。
2．然后取出后面数列中的2，明显！这个2和前面的3，5都可以组成逆序数对即3和2，5和2都是逆序数对。
3．然后取出前面数列中的3。
4．然后取出后面数列中的4，同理，可知这个4和前面数列中的5可以组成一个逆序数对。
这样就完成了逆序数对的统计，归并排序的时间复杂度是O(N * LogN)，因此这种从归并排序到数列的逆序数对的解法的时间复杂度同样是O(N * LogN)，下面给出代码：

//从归并排序到数列的逆序数对
#include <stdio.h>
int g_nCount;
void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;

    while (i <= m && j <= n) //a[i] 前面的数  a[j] 后面的数
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
        {
            temp[k++] = a[j++];
            //a[j]和前面每一个数都能组成逆序数对
            g_nCount += m - i + 1;
        }
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);    //左边有序
        mergesort(a, mid + 1, last, temp); //右边有序
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并
    }
}

void MergeSort(int a[], int n)
{
    int *p = new int[n];
    mergesort(a, 0, n - 1, p);

}

Sort List

    ListNode *sortList(ListNode *head) {
        if(!head||!head->next) return head;
        ListNode*fast,*slow;
        fast=slow=head;
        while(fast->next&&fast->next->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode*head2=slow->next;
        slow->next=NULL;
        head=sortList(head);
        head2=sortList(head2);
        return merge(head,head2);
    }
//insert the nodes of l2 into l1
    ListNode*merge(ListNode*l1,ListNode*l2){
        ListNode dummy(0),*prev=&dummy;
        dummy.next=l1;
        while(l2&&prev->next){
            if(l2->val<prev->next->val){
                ListNode*ne=l2->next;
                l2->next=prev->next;
                prev->next=l2;
                l2=ne;
            }
            prev=prev->next;
        }
        if(prev->next==NULL)
            prev->next=l2;
        return dummy.next;
    }

//another flavor of merge function, from annikim
    ListNode*merge(ListNode*l1,ListNode*l2){
        ListNode dummy(0),*last=&dummy;
        while(l1&&l2){
            ListNode**min=l1->val<l2->val?&l1:&l2;
            last->next=*min;
            last=last->next;
            *min=(*min)->next;
        }
        if(l1)
            last->next=l1;
        if(l2)
            last->next=l2;
        return dummy.next;   
    }

Merge k Sorted Lists

two methods are provided. The first one is like merge sort. The time complexity is T(k)=2T(k/2)+O(n*k), thus T(k)=O(nklogk).  The space complexity is the recursive stack O(logk).
The second one uses a minimum heap. Every node is read once. Every time we get the top node from the heap, we need to add  a  new one. So the time complexity is O(nklogk), which is the same as the first one. The space complexity is the size of the heap, which is O(k).

//first one

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.empty())
        {
            return NULL;
        }
           
        return mergeKLists2(lists,0,lists.size()-1);
   
    }  
    ListNode *mergeKLists2(vector<ListNode *> &lists,int start,int end) {
        if(start==end)
            return lists[start];
        return mergeTwoLists(mergeKLists2(lists,start,(start+end)/2),mergeKLists2(lists,(start+end)/2+1,end));
   
    }
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy(0),*pre=&dummy;
        pre->next=l1;
        while(l1&&l2){
            if(l1->val>l2->val){
                ListNode*next=l2->next;
                l2->next=pre->next;
                pre->next=l2;
                l2=next;
            }
            else
                l1=l1->next;
            pre=pre->next;   
        }
        if(l2) pre->next=l2;
        return dummy.next;
    }

};

//second method, remember that the default priority_queue is maximum heap.

class Mycompare { public:     bool operator()(ListNode *a, ListNode *b) {         return a->val > b->val;     } }; class Solution { public:     ListNode *mergeKLists(vector<ListNode *> &lists) {         priority_queue<ListNode *, vector<ListNode *>, Mycompare> q;         for (int i = 0; i < lists.size(); ++i)             if (lists[i])                 q.push(lists[i]);         ListNode dummy(0), *cur = &dummy;         while (!q.empty()) {             ListNode *node = q.top();             q.pop();             cur = cur->next = node;             if (node->next)                 q.push(node->next);         }         return dummy.next;     } };

Merge Two Sorted Lists

  use a dummy node
维护两个指针对应两个链表，因为一般会以一条链表为基准，比如说l1, 那么如果l1当前元素比较小，那么直接移动l1即可，否则将l2当前的元素插入到l1当前元素的前面。算法时间复杂度是O(m+n),m和n分别是两 条链表的长度，空间复杂度是O(1)，代码如下：

    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy(0);dummy.next=l1;
        ListNode*prev=&dummy;
        while(l2&&prev->next){
            if(l2->val<prev->next->val){
                ListNode* ne=l2->next;
                l2->next=prev->next;
                prev->next=l2;
                l2=ne;
            }
            prev=prev->next;
        }
        if(prev->next==NULL)
            prev->next=l2;
        return dummy.next;  
    }