Another Divide-and-Conquer Sort
Mergesort
Mergesort
lSort
by successively merging longer and longer sorted sequences.
lUseful
with linked lists, or large files.
lMore
difficult to program for arrays.
lDifferent
versions exists:
lTop-Down: Split unordered sequence,
vs.
lBottom-Up: Start with sequences of
length 1 and
create increasingly longer ones.