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