To Sort the values in an array
X between positions FIRST and LAST. Choose some base cases:
- FIRST=LAST:
- nothing needs to be done.
- FIRST+1=LAST:
- there are 2 numbers to be sorted; compare them and, if they are
out of order, swap them.
Otherwise:
- P1: sort the numbers in X between positions FIRST and M; the
answer is S1.
- P2: sort the numbers in X between positions M+1 and LAST; the
answer is S2.
- Combine: S = Merge S1 and S2.
- M = 1:
- Insertion Sort.
- M = midpoint between FIRST and LAST:
- Merge Sort.
Both are correct, but their efficiency is very different: Merge Sort
is extremely fast (optimal in fact), whereas Insertion Sort is very
slow.