Merge Sort

Merge sort is a classic divide and conquer algorithm. It splits an array in half, recursively sorts each half, and finally merges them together. This algorithm has excellent performance but has higher memory usage requirements because it generates an entirely new array instead of rearranging existing values.

History

John von Neumann discovered merge-sort in 1945

Applications

  • Countless general purpose programming tasks
  • Building block for several primitive data types including strings, matrices, and mathematical vectors
  • Building block for several more complex data structures including heap, bloom filter, and hash table

Asymptotic Complexity

$O(n \lg_{2}n)$

Pseudo Code

sort:
    A = input array
    returns: New array consisting of sorted values

    if length of A == 1:
        return A

    A1 = first half of A
    A2 = second half of A

    sort(A1)
    sort(A2)

    return merge(A1, A2)

merge:
    A1 = sorted array
    A2 = sorted array
    returns: new array with values merged from A1 and A1

    i = 1
    j = 1

    for k = 1 to n
        if A1[i] < A2[j]
            B[k] = A1[i]
            i++
        else
            B[k] = A2[j]
            j++

    return B
            

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions