For integer linked lists, compare their heads and copy the smaller head, retaining the other list for the next step:This merge algorithm preserves duplicates and chooses the left list on a tie, making it stable when elements have an ordering key. Each recursive step decreases the combined length. For correctness, the chosen head is no greater than either remaining head and therefore no greater than any remaining element; structural induction then proves that the result is ordered and contains exactly the elements of both inputs. For other element types, replace the integer comparison by a supplied ordering function. Merge repeatedly emits the smaller head and reuses the remaining list when the other becomes empty.
fun merge ([], ys) = ys
| merge (xs, []) = xs
| merge (xs as x :: xt, ys as y :: yt) =
if x <= y then x :: merge (xt, ys)
else y :: merge (xs, yt);Split the list into two contiguous halves, sort each recursively, and use the merge algorithm from part (a):
fun mergesort [] = []
| mergesort [x] = [x]
| mergesort xs =
let
val k = List.length xs div 2
val left = List.take (xs, k)
val right = List.drop (xs, k)
in
merge (mergesort left, mergesort right)
end;List.length counts elements, List.take(xs,k) returns the first elements and List.drop(xs,k) returns the remaining suffix. Since when , both recursive inputs are smaller and differ in length by at most one. Mathematical induction on length proves that each half is sorted without losing elements, and the correctness of the merge algorithm proves the same for the combined result. Contiguous splitting and left-biased equal-key merging preserve the original relative order of equal keys. This is a stable top-down merge sort.Assume head comparison and construction of one list cell take constant time. In the merge algorithm, every comparison removes one head from the recursive inputs, and evaluation stops as soon as either is empty. For lengths , at most comparisons and the same number of newly constructed cells are required; the untouched suffix is shared. Inputs which keep both lists nonempty until the last comparison attain this bound. ThusAn initially empty input makes this particular implementation constant-time; not every pair requires linear work.
The balanced merge sort spends time per call on list length, splitting and merging. Hence its time complexity satisfiesAt each recursion level the lengths of its disjoint subproblems sum to , so the work per level is , and balanced splitting gives levels. ConsequentlyThe length and splitting traversals change the constant factor, not this asymptotic order; repeatedly inserting elements into a sorted list would not give the same complexity.
Articles by others on the same topic
There are currently no matching articles.