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.
John von Neumann discovered merge-sort in 1945
- 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
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
Click here for build and run instructions