Merge sort incorporates two main ideas to improve its runtime:
Example: Using merge sort to sort a list of integers contained in an array:
Suppose we have an array A with n indices ranging from to . We apply merge sort to and where c is the integer part of . When the two halves are returned they will have been sorted. They can now be merged together to form a sorted array.
In a simple pseudocode form, the algorithm could look something like this:
var list left, right, result
if length(m) ≤ 1
var middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
There are several variants for the
merge() function, the simplest variant could look like this:
var list result
while length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
append first(right) to result
right = rest(right)
while length(left) > 0
append left to result
while length(right) > 0
append right to result
In sorting n items, merge sort has an average and worst-case performance of O(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists). The closed form follows from the master theorem.
In the worst case, merge sort does approximately (n ⌈lg n⌉ - 2⌈lg n⌉ + 1) comparisons, which is between (n lg n - n + 1) and (n lg n + n + O(lg n)).
For large n and a randomly ordered input list, merge sort's expected (average) number of comparisons approaches α·n fewer than the worst case where
In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case; merge sort always makes fewer comparisons than quicksort, except in extremely rare cases, when they tie, where merge sort's worst case is found simultaneously with quicksort's best case. In terms of moves, merge sort's worst case complexity is O(n log n)—the same complexity as quicksort's best case, and merge sort's best case takes about half as many iterations as the worst case.
Recursive implementations of merge sort make 2n - 1 method calls in the worst case, compared to quicksort's n, thus has roughly twice as much recursive overhead as quicksort. However, iterative, non-recursive, implementations of merge sort, avoiding method call overhead, are not difficult to code. Merge sort's most common implementation does not sort in place; therefore, the memory size of the input must be allocated for the sorted output to be stored in.
Sorting in-place is possible but is very complicated, and will offer little performance gains in practice, even if the algorithm runs in O(n log n) time. In these cases, algorithms like heapsort usually offer comparable speed, and are far less complex. Additionally, unlike the standard merge sort, in-place merge sort is not a stable sort.
Merge sort is more efficient than quicksort for some types of lists if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages such as Lisp, where sequentially accessed data structures are very common. Unlike some (efficient) implementations of quicksort, merge sort is a stable sort as long as the merge operation is implemented properly.
As can be seen from the procedure merge sort, there are some complaints. One complaint we might raise is its use of 2n locations; the additional n locations were needed because one couldn't reasonably merge two sorted sets in place. But despite the use of this space the algorithm must still work hard, copying the result placed into Result list back into m list on each call of merge . An alternative to this copying is to associate a new field of information with each key (the elements in m are called keys). This field will be used to link the keys and any associated information together in a sorted list (a key and its related information is called a record). Then the merging of the sorted lists proceeds by changing the link values; no records need to be moved at all. A field which contains only a link will generally be smaller than an entire record so less space will also be used.
For the same reason it is also useful for sorting data on disk that is too large to fit entirely into primary memory. On tape drives that can run both backwards and forwards, merge passes can be run in both directions, avoiding rewind time.
If you have four tape drives, it works as follows:
For almost-sorted data on tape, a bottom-up "natural merge sort" variant of this algorithm is popular.
The bottom-up "natural merge sort" merges whatever "chunks" of in-order records are already in the data. In the worst case (reversed data), "natural merge sort" performs the same as the above -- it merges individual records into 2-record chunks, then 2-record chunks into 4-record chunks, etc. In the best case (already mostly-sorted data), "natural merge sort" merges large already-sorted chunks into even larger chunks, hopefully finishing in fewer than log n passes.
In a simple pseudocode form, the "natural merge sort" algorithm could look something like this:
# Original data is on the input tape; the other tapes are blank
function merge_sort(input_tape, output_tape, scratch_tape_C, scratch_tape_D)
while any records remain on the input_tape
while any records remain on the input_tape
merge(input_tape, output_tape, scratch_tape_C)
merge(input_tape, output_tape, scratch_tape_D)
while any records remain on C or D
merge(scratch_tape_C, scratch_tape_D, output_tape)
merge(scratch_tape_C, scratch_tape_D, input_tape)
# take the next sorted chunk from the input tapes, and merge into the single given output_tape.
# tapes are scanned linearly.
# tape[next] gives the record currently under the read head of that tape.
# tape[current] gives the record previously under the read head of that tape.
# (Generally both tape[current] and tape[previous] are buffered in RAM ...)
function merge(left, right, output_tape)
if left[current] ≤ right[current]
append left[current] to output_tape
read next record from left tape
append right[current] to output_tape
read next record from right tape
while left[current] < left[next] and right[current] < right[next]
if left[current] < left[next]
append current_left_record to output_tape
if right[current] < right[next]
append current_right_record to output_tape
Either form of merge sort can be generalized to any number of tapes.
M.A. Kronrod suggested in 1969 an alternative version of merge sort that used constant additional space.
As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch when fewer than seven array elements are being sorted.
US Patent Issued to Kousokuya on Dec. 11 for "Bit String Merge Sort Device, Method, and Program" (Japanese Inventors)
Dec 13, 2012; ALEXANDRIA, Va., Dec. 13 -- United States Patent no. 8,332,410, issued on Dec. 11, was assigned to Kousokuya Inc. (Kanagawa,...
US Patent Issued to SAP on Sept. 4 for "SIMD Merge-Sort and Duplicate Removal Operations for Data Arrays" (Japanese Inventors)
Sep 09, 2012; ALEXANDRIA, Va., Sept. 9 -- United States Patent no. 8,261,043, issued on Sept. 4, was assigned to SAP AG (Walldorf, Germany)....