Merge Sort and Quick Sort

This lesson covers merge sort and quick sort — two efficient, divide-and-conquer sorting algorithms in the OCR A-Level Computer Science (H446) specification. These algorithms are significantly faster than bubble sort and insertion sort for large data sets.

---

Divide and Conquer

Both merge sort and quick sort use the divide and conquer strategy:

1. Divide — split the problem into smaller subproblems.
2. Conquer — solve each subproblem (often recursively).
3. Combine — merge the solutions to form the final answer.

---

Merge Sort

Merge sort works by:

1. Dividing the list in half repeatedly until each sublist has one element.
2. Merging adjacent sublists back together in sorted order.

Algorithm

1. If the list has 0 or 1 elements, it is already sorted — return it.
2. Split the list into two halves.
3. Recursively sort each half.
4. Merge the two sorted halves into one sorted list.

Pseudocode (OCR Style)

function mergeSort(data)
    if data.length <= 1 then
        return data
    endif
    mid = data.length DIV 2
    left = mergeSort(data[0..mid-1])
    right = mergeSort(data[mid..data.length-1])
    return merge(left, right)
endfunction

function merge(left, right)
    result = []
    i = 0
    j = 0
    while i < left.length AND j < right.length
        if left[i] <= right[j] then
            result.append(left[i])
            i = i + 1
        else
            result.append(right[j])
            j = j + 1
        endif
    endwhile
    // Append remaining elements
    while i < left.length
        result.append(left[i])
        i = i + 1
    endwhile
    while j < right.length
        result.append(right[j])
        j = j + 1
    endwhile
    return result
endfunction

Python Implementation

def merge_sort(data):
    if len(data) <= 1:
        return data
    mid = len(data) // 2
    left = merge_sort(data[:mid])
    right = merge_sort(data[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Worked Example

Sort [6, 3, 8, 1, 5, 2, 7, 4]:

Division phase:

[6, 3, 8, 1, 5, 2, 7, 4]
       /               \
[6, 3, 8, 1]      [5, 2, 7, 4]
   /      \          /      \
[6, 3]  [8, 1]   [5, 2]  [7, 4]
 / \     / \      / \     / \
[6] [3] [8] [1]  [5] [2] [7] [4]

Merge phase:

[6] [3] [8] [1]  [5] [2] [7] [4]
 \ /     \ /      \ /     \ /
[3, 6]  [1, 8]   [2, 5]  [4, 7]
   \      /          \      /
[1, 3, 6, 8]      [2, 4, 5, 7]
       \               /
[1, 2, 3, 4, 5, 6, 7, 8]

Time Complexity

Case	Complexity	Explanation
Best	O(n log n)	Always divides and merges
Worst	O(n log n)	Always divides and merges
Average	O(n log n)	Always divides and merges

Space Complexity: O(n) — requires additional space for the merged sublists.

Why O(n log n)?

• log n levels of division (halving n items gives log2(n) levels).
• At each level, n comparisons are made during merging.
• Total: n x log n = O(n log n).

---

Quick Sort

Quick sort works by:

1. Choosing a pivot element.
2. Partitioning the list: elements smaller than the pivot go left, larger go right.
3. Recursively sorting the left and right partitions.

Algorithm

1. If the list has 0 or 1 elements, it is already sorted — return it.
2. Choose a pivot (commonly the first, last, or middle element).
3. Partition: place all elements less than the pivot before it, and all greater after it.
4. Recursively sort the left partition and the right partition.

Pseudocode (OCR Style)

function quickSort(data, low, high)
    if low < high then
        pivotIndex = partition(data, low, high)
        quickSort(data, low, pivotIndex - 1)
        quickSort(data, pivotIndex + 1, high)
    endif
endfunction

function partition(data, low, high)
    pivot = data[high]
    i = low - 1
    for j = low to high - 1
        if data[j] <= pivot then
            i = i + 1
            swap data[i] and data[j]
        endif
    next j
    swap data[i + 1] and data[high]
    return i + 1
endfunction

Python Implementation