Introduction to Algorithms (Insertion Sort, Merge Sort)

The problem of sorting

Input: array A[1…n] of numbers.

Output: permutation B[1…n] of A such that B[1] ≤ B[2] ≤ … ≤ B[n] .

Why Sorting

• Obvious applications
• Problems that become easy once items are in sorted order

Insertion Sort

Insertion-Sort(A, n):
    for j ← 2 to n:
        insert key A[j] into the (already sorted) sub-array A[1 .. j-1].
        by pairwise key-swaps down to its right position

Merge Sort

Merge-Sort A[1 .. n]:
    1. If n = 1, done (nothing to sort).
    2. Otherwise, recursively sort A[1 .. n/2] and A[n/2+1 .. n].
    3. “Merge” the two sorted sub-arrays.