Merge Sort

Merge Sort

Merge sort is a recursive Divide & Conquer algorithm that essentially divides a given array into two halves, sorts those halves, and merges them together in order. The base case is to merge two arrays of size 1 so, eventually, single elements are merged in order; the merge part is where most of the heavy lifting happens.

Pseudocode

mergeSort(arr)
  if arr.length == 1
    return arr
  else:
    s1 = mergeSort(arr[0,n/2])
    s2 = mergeSort(arr[n/2+1,n])
 return merge(s1,s2)

Attribution: Wikipedia under CC-BY-SA 3.0