Merge Sort Algorithm

This is the Merge Sort Algorithm.

MergeSort is based on a simple "Divide and Conquer" approach. The principle behind it is simple: We want to sort an entire list, but if this entire list is sorted, then each half of this list must also be sorted. It is an easier problem to sort a smaller list than a larger list, so we sort each of the smaller lists. Once these two lists are sorted, we run a merge algorithm which combines the two smaller lists into one larger list. These smaller lists are then sorted using the same principle until our smaller lists are of size 1 or 2, in which case we can simply swap the two items or return the item itself.

The pseudocode for this algorithm is as follows:
MergeSort(A, start, end)
     if ((end - start + 1) = 1)
          return A
     end if

     mid <- (end - start) / 2

     left <- {A[start], A[start+1], ... A[mid]}
     right <- {A[mid+1], A[mid+2], ... A[end]

     left <- MergeSort(left, 0, mid)
     right <- MergeSort(right, 0, end-mid)

     return Merge(left, right)
end MergeSort

Show Work?