Insertion Sort and Merge Sort

Insertion sort maintains a sorted sub-list at the left of the array. At the start, the sorted sub-list contains just the first element (a single element is trivially sorted). The algorithm then takes each subsequent element - the key - and inserts it into the correct position in the sorted sub-list by shifting larger elements one position to the right.

This is exactly how most people sort a hand of cards: the sorted sub-list is the cards you are already holding in order, and the key is the next card you pick up.

Trace insertion sort on [5, 2, 8, 1, 9]:

Bold = confirmed sorted portion. The list is fully sorted after 4 insertions (n-1 insertions for n elements).

// Insertion sort - ascending order (AQA)
SUBROUTINE insertionSort(myList)
    n ← LEN(myList)
    FOR i ← 1 TO n - 1
        key ← myList[i]    // Element to insert
        j ← i - 1
        WHILE j >= 0 AND myList[j] > key
            myList[j+1] ← myList[j]    // Shift right
            j ← j - 1
        ENDWHILE
        myList[j+1] ← key    // Insert key in correct position
    ENDFOR
    RETURN myList
ENDSUBROUTINE

# Insertion sort - ascending order (OCR)
procedure insertionSort(myList)
    n = len(myList)
    for i = 1 to n - 1
        key = myList[i]
        j = i - 1
        while j >= 0 and myList[j] > key
            myList[j+1] = myList[j]
            j = j - 1
        end while
        myList[j+1] = key
    next i
    return myList
endprocedure

Merge sort is a divide-and-conquer algorithm. It works in two phases:

Phase 1 - Divide: Repeatedly split the list in half until you have sub-lists of length 1. A list of one element is trivially sorted.

Phase 2 - Merge: Repeatedly merge pairs of sorted sub-lists into larger sorted lists. When merging two sorted lists, always take the smallest remaining element from the front of either list.

Sorting [38, 27, 43, 3, 9, 82, 10]:

The key to merge sort is the merge step: given two sorted lists, produce one sorted list. Compare the first element of each list; take whichever is smaller and add it to the result. Repeat until one list is empty, then append the remainder of the other list.

// Merge two sorted sub-lists into one sorted list (AQA)
FUNCTION merge(left, right)
    result ← []
    WHILE LEN(left) > 0 AND LEN(right) > 0
        IF left[0] <= right[0] THEN
            result.append(left[0])
            left ← left[1:]    // Remove first element
        ELSE
            result.append(right[0])
            right ← right[1:]
        ENDIF
    ENDWHILE
    result ← result + left + right    // Append any remaining
    RETURN result
ENDFUNCTION

# Merge two sorted lists (OCR)
function merge(left, right)
    result = []
    while len(left) > 0 and len(right) > 0
        if left[0] <= right[0] then
            result.append(left[0])
            left = left[1:]
        else
            result.append(right[0])
            right = right[1:]
        end if
    end while
    result = result + left + right
    return result
endfunction

* Bubble sort best case is O(n) only with early termination. * Binary search is a searching algorithm, not a sorting algorithm - included for reference.