OCR A Level CS 2.3.3 Sorting Algorithms

What is the purpose of sorting algorithms?

To arrange a collection of elements into a specific order, usually ascending or descending.

What are the four main sorting algorithms in OCR A-Level?

✅ Bubble Sort
✅ Insertion Sort
✅ Merge Sort
✅ Quick Sort

How does bubble sort work?

Compares adjacent elements and swaps them if they are in the wrong order. This continues until the list is sorted.

What is the time complexity of bubble sort?

O(n²) (Quadratic) – very slow for large lists.

How can bubble sort be optimized?

By adding a noSwap flag to stop sorting early if no swaps occur in a pass.

How does insertion sort work?

Builds a sorted list by inserting each new element into its correct position in the sorted part.

What is the time complexity of insertion sort?

O(n²) – inefficient for large lists but fast for nearly sorted data.

How does insertion sort compare to bubble sort?

More efficient, as it only makes necessary swaps.

How does merge sort work?

Uses divide and conquer – splits the list into halves, recursively sorts them, then merges them back together.

What is the time complexity of merge sort?

O(n log n) – much faster than bubble and insertion sort.

What is the drawback of merge sort?

It requires extra memory for storing sublists.

How does quick sort work?

Chooses a pivot, then partitions elements into smaller or larger than the pivot, and recursively sorts both parts.

What is the time complexity of quick sort?

O(n²) in worst case, but O(n log n) on average

When is quick sort faster than merge sort?

When memory usage is a concern, as quick sort is in-place (doesn’t use extra memory).