Merge Sort

Idea

Divide the N element sequence into subarray A[1...N/2] and A[N/2+1...N].
Conquer/Solve/Sort each of the 2 subarray's using Divide step recursively
    - till you reach a base-case/trivial-problem
Combine the solutions/sorted-arrays received from solving each of the subproblems.

Merge sort follows divide-and-conquer approach.
Another version:
For each level, we look at an array which initially has elements 
in unsorted order and we would try and split the array into equal parts, 
then sort each of those arrays. We need to also do the combine step to 
combining the two sorted arrays.

Pseudo code

MERGE_SORT (A, start, end):
    if (start < end)
        return
    mid = start + (end - start)/2
    MERGE_SORT (A, start, mid) // Closed interval
    MERGE_SORT (A, mid+1, end) // Closed interval
    MERGE_SORT_COMBINE (A, start, mid, end)
    return

Confused pseudocode implementation
MERGE_SORT_COMBINE (A, start, mid, end):
    //**Instead of using P,Q,R you could have used L and R for left and right subarray
    //**Instead of using R we could use the same array A
    //**What is the size of P, we know P = A[start...end] does it mean we make a copy.
        //**Its not clear from the pseudo code
    //**Define how many elements you want to copy instead of say start...mid 
    //**Instead of using 2 extra while loops at the end, we could use an array element in the end to indicate INF/sentinel value
    P = A[start ... mid] // Half open interval, size is mid-start+1
    Q = A[mid+1 ... end] // Half open interval
    R = new array of size: [1 ... end-start]    
    I = start
    J = mid+1
    K = start
    while I < mid AND J < end AND I < J // Half open interval
        if P[I] < Q[J]
            R[K] = P[I]
            I += 1
        else if P[I] > Q[J]
            R[K] = Q[J]
            J += 1
        K += 1
    while I < mid // Half open interval
        R[K] = P[I]
        I += 1
        K += 1
    while J < end // Half open interval
        R[K] = Q[J]
        J += 1
        K += 1
    COPY R into A[start...end]
    return

// Final/improved merge sort
MERGE_SORT_COMBINE (A, p, q, r):
    n1 = q - p + 1
    n2 = r - (q + 1) - 1
    L = size(1...n1+1) //+1 to include sentinel INF value
    R = size(1...n2+1) //+1 to include sentinel INF value

    L = copy(A[p...q] into L[1...n1])   //closed interval(both inclusive)
    R = copy(A[q+1...r] into R[1...n2]) //closed interval(both inclusive) 

    L[n1+1] = INF
    R[n2+1] = INF

    I = 1
    J = 1
    K = 0
    for K = p to r: //closed interval(both inclusive)
        if L[I] < R[J]
            A[K] = L[I]
            I += 1
            K += 1
        else R[J] < L[I]
            A[K] = R[J]
            J += 1
            K += 1
    return

Loop Invariant

Its a recursion tree/problem.

Loop invariant is available within the 'combine' step of the divide-and-conquer 
algorithm. Array L[1...n1] and R[1...n2]are sorted. 

During each iteration from K = p to r, we look at each of 
the n1 elements within L and compare it to each of the n2 elements 
within R - and copy the lowest element with A. In doing so, we are 
effectively using insertion sort method to find the lowest of between 
two arrays and inserting it with A.

At the start of each iteration of the for loop, the subarray A contains K-p smallest elements of L[1...n1] and R[1...n2] in sorted order. AND

L[i] and R[j] are the smallest elements of their arrays that have not been copied back to A.

Initialization

Prior to first iteration, we have k = p ie A[p...k-1] is empty. This empty subarray contains 0 smallest elements L and R.

Maintenance

Termination

Code

Big-O Analysis

As per master's theorem, we can come up with an equation