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.
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