Merge sort (also commonly spelled as mergesort or merge-sort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations of merge sort are stable, which means that the relative order of equal elements is the same between the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.
Algorithm Conceptually, a merge sort works as follows:
Divide the unsorted list into n sub-lists, each containing one element (a list of one element is considered sorted). Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list. Merge sort is efficient because merging and sorting two sublists can be performed in linear time, provided that the sublists are already sorted.
Top-down implementation Example C-like code using indices for top-down merge sort algorithm that recursively splits the list into sublists (called runs in this example) until sublist size is 1, then merges those sublists to produce a sorted list. The copy back step is avoided with alternating the direction of the merge with each level of recursion (except for an initial one-time copy, that can be avoided too). As a simple example, consider an array with two elements. The elements are copied to b, then merged back to a. If there are four elements, when the bottom of the recursion level is reached, single element runs from a are merged to b, and then at the next higher level of recursion, those two-element runs are merged to a. This pattern continues with each level of recursion.
Sorting the entire array is accomplished by topDownMergeSort(a, b, a.length).
Bottom-up implementation Example C-like code using indices for bottom-up merge sort algorithm which treats the list as an array of n sublists (called runs in this example) of size 1, and iteratively merges sub-lists back and forth between two buffers:
Top-down implementation using lists Pseudocode for top-down merge sort algorithm which recursively divides the input list into smaller sublists until the sublists are trivially sorted, and then merges the sublists while returning up the call chain.
function merge_sort(list m) is // Base case. A list of zero or one elements is sorted, by definition. if length of m ≤ 1 then return m
// Recursive case. First, divide the list into equal-sized sublists // consisting of the first half and second half of the list. // This assumes lists start at index 0. var left := empty list var right := empty list for each x with index i in m do if i < (length of m)/2 then add x to left else add x to right
// Recursively sort both sublists. left := merge_sort(left) right := merge_sort(right)
// Then merge the now-sorted sublists. return merge(left, right)
In this example, the merge function merges the left and right sublists.
function merge(left, right) is var result := empty list
while left is not empty and right is not empty do if first(left) ≤ first(right) then append first(left) to result left := rest(left) else append first(right) to result right := rest(right)
// Either left or right may have elements left; consume them. // (Only one of the following loops will actually be entered.) while left is not empty do append first(left) to result left := rest(left) while right is not empty do append first(right) to result right := rest(right) return result
Bottom-up implementation using lists Pseudocode for bottom-up merge sort algorithm which uses a small fixed size array of references to nodes, where array[i] is either a reference to a list of size 2i or nil. node is a reference or pointer to a node. The merge() function would be similar to the one shown in the top-down merge lists example, it merges two already sorted lists, and handles empty lists. In this case, merge() would use node for its input parameters and return value.
function merge_sort(node head) is // return if empty list if head = nil then return nil var node array[32]; initially all nil var node result var node next var int i result := head // merge nodes into array while result ≠ nil do next := result.next; result.next := nil for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do result := merge(array[i], result) array[i] := nil // do not go past end of array if i = 32 then i -= 1 array[i] := result result := next // merge array into single list result := nil for (i = 0; i < 32; i += 1) do result := merge(array[i], result) return result
Top-down implementation in a declarative style Haskell-like pseudocode, showing how merge sort can be implemented in such a language using constructs and ideas from functional programming.
Analysis
… excerpt ends here. Continue reading the full article.
