# Standard sorting algorithms

> Computer Science · CIE A-Level 9618
> Source: https://www.owlsprep.com/study/cie-9618-u9-standard-sorting-algorithms/

This module covers the five standard sorting algorithms required for CIE 9618, their core properties, time/space complexity, and tracing rules. You will learn to compare algorithms for different use cases and answer common exam questions.

**Prerequisites:** [Basic algorithm tracing and pseudocode](https://www.owlsprep.com/study/cie-9618-u3-algorithm-pseudocode/); [Asymptotic time and space complexity](https://www.owlsprep.com/study/cie-9618-u9-time-space-complexity/)

## Learning objectives

- Describe the operation of bubble, insertion, selection, merge and quicksort
- Trace the execution of each standard sorting algorithm on a sample input
- Compare the time, space and behavioural properties of each sorting algorithm
- Select the appropriate sorting algorithm for a given problem use case

## Simple Quadratic-Time Sorting Algorithms

**Simple Sorting Algorithms** — A group of in-place quadratic-time sorting algorithms, valued for their simplicity. Suitable for small or nearly sorted datasets, includes bubble, insertion and selection sort.

*Example:* Insertion sort is often used to sort small datasets in more complex algorithms

All three simple algorithms incrementally build a sorted portion of the input array, modifying the array in-place to avoid extra memory overhead. Each algorithm has a different approach to expanding the sorted portion.

**Worked example:** Sort the array $[4, 2, 7, 1]$ using insertion sort, show all intermediate steps.

1. Start with the first element as the sorted portion
2. Initial state: $[4 \mid 2, 7, 1]$
3. Take the next unsorted element 2, shift 4 right, insert 2 into the sorted portion
4. State after step 1: $[2, 4 \mid 7, 1]$
5. Take next unsorted element 7, it is larger than 4, insert at the end of the sorted portion
6. State after step 2: $[2, 4, 7 \mid 1]$
7. Take next unsorted element 1, shift 7, 4, 2 right, insert 1 at the start of the sorted portion
8. Final sorted array: $[1, 2, 4, 7]$

> **tip**
>
> Bubble sort works by repeatedly swapping adjacent out-of-order elements, bubbling the largest unsorted element to its correct position each full pass.

> **Exam tip:** When asked to count passes or swaps for bubble sort, count each full pass through the unsorted portion as one pass, not individual swaps.

*Calculator:* forbidden

## Merge Sort: Divide-and-Conquer Sorting

**Merge Sort** — A stable divide-and-conquer sorting algorithm that recursively splits the input into two halves, sorts each half, then merges the two sorted halves into one sorted array.

*Example:* Merge sort is ideal for sorting linked lists, where merging is cheap

Merge sort's consistent performance makes it a reliable choice for large datasets. Unlike quicksort, its time complexity is the same regardless of the initial order of the input.

**Worked example:** Sort $[3, 1, 4, 2]$ using merge sort, show the split and merge steps.

1. Split the original array into two equal halves
2. Split result: $[3, 1]$ and $[4, 2]$
3. Split each half into single-element subarrays (trivially sorted)
4. Split result: $[3], [1], [4], [2]$
5. Merge the first pair: compare 3 and 1, resulting sorted subarray $[1, 3]$
6. Merge the second pair: compare 4 and 2, resulting sorted subarray $[2, 4]$
7. Merge the two sorted subarrays: take 1, 2, 3, 4
8. Final sorted array: $[1, 2, 3, 4]$

> **info**
>
> Standard merge sort is not in-place, requiring $O(n)$ extra memory to store temporary merged subarrays.

*Calculator:* forbidden

## Quicksort: Partition-Based Divide-and-Conquer Sorting

**Quicksort** — An in-place divide-and-conquer sorting algorithm that selects a pivot element, partitions the array into elements less than the pivot and elements greater than the pivot, then recursively sorts the partitions.

*Example:* Quicksort is often the default sorting algorithm for general-purpose in-memory sorting due to its good average performance

Pivot selection is critical to quicksort's performance. Common pivot choices include first element, last element, middle element, or a random element. Poor pivot selection leads to worst-case quadratic time.

**Worked example:** Sort $[5, 2, 6, 1, 3]$ using quicksort with the last element as pivot each step.

1. Original array: $[5, 2, 6, 1, 3]$, pivot = 3
2. Partition: elements < 3 = $[2, 1]$, pivot, elements > 3 = $[5, 6]$
3. Recurse on left partition $[2, 1]$, pivot = 1
4. Partition: elements < 1 = $[]$, pivot = 1, elements > 1 = $[2]$, sorted
5. Merge left partition result: $[1, 2]$$
6. Recurse on right partition $[5, 6]$, pivot = 6, sorted result $[5, 6]$
7. Merge all parts: left + pivot + right = $[1, 2, 3, 5, 6]$
8. Final sorted array: $[1, 2, 3, 5, 6]$

> **Exam tip:** Always show the partition step after each pivot selection when tracing quicksort, this is where most of the marks are awarded.

*Calculator:* forbidden

## Comparing Sorting Algorithm Properties

When answering compare questions in the exam, you need to reference four core properties: time complexity (best/average/worst), space complexity, whether the algorithm is in-place, and whether it is stable.

| Algorithm | Best Time | Average Time | Worst Time | In-place? | Stable? |
| --- | --- | --- | --- | --- | --- |
| Bubble sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | Yes | Yes |
| Insertion sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | Yes | Yes |
| Selection sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | Yes | No |
| Merge sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | No | Yes |
| Quicksort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | Yes | No |

**Check your understanding**

Check your understanding of core properties:

1. Which algorithm always has $O(n \log n)$ worst-case time complexity?

   - Bubble sort
   - Merge sort
   - Quicksort
   - Insertion sort

   *Answer:* Merge sort

   *Why:* Correct! Merge sort always splits the input into equal halves, so it always has $O(n \log n)$ time regardless of input order.

2. Which of these algorithms is NOT in-place?

   - Quicksort
   - Insertion sort
   - Merge sort
   - Selection sort

   *Answer:* Merge sort

   *Why:* Correct! Standard merge sort requires extra $O(n)$ memory to store temporary merged subarrays.

**Exam command terms**

Common exam command terms for this topic:

- **Trace** — Show every step of the algorithm execution, including all intermediate array states *(Trace 2 passes of bubble sort on the input)*

- **Compare** — State similarities and differences between algorithms, including complexity and properties *(Compare quicksort and merge sort for large datasets)*

*Calculator:* forbidden

## Common pitfalls

- **Wrong:** Claiming quicksort is always $O(n \log n)$ time
  - Why it fails: Quicksort degrades to $O(n^2)$ time with poor pivot selection on sorted/reverse-sorted input
  - Correct: State that average time is $O(n \log n)$ and worst-case time is $O(n^2)$ for quicksort
- **Wrong:** Forgetting that standard merge sort is not in-place
  - Why it fails: This is a common exam question that tests knowledge of core algorithm properties
  - Correct: Remember merge sort requires $O(n)$ extra memory, so it is not an in-place algorithm
- **Wrong:** Counting the wrong number of passes for bubble sort
  - Why it fails: A common mistake is counting individual swaps as passes, leading to lost marks
  - Correct: A full pass processes all unsorted elements, so n elements need at most n-1 passes
- **Wrong:** Claiming all in-place sorting algorithms are stable
  - Why it fails: Stability depends on swap implementation, not whether sorting is in-place
  - Correct: Memorize that selection sort and quicksort are unstable, bubble, insertion and merge are stable
- **Wrong:** Merging before splitting recursively in merge sort
  - Why it fails: Many students mix up the order of operations for divide-and-conquer algorithms
  - Correct: Split the array first, recursively sort each half, then merge the sorted halves

## Cheatsheet

| Algorithm | Worst Time | In-place? | Stable? |
| --- | --- | --- | --- |
| Bubble | $n^2$ | Y | Y |
| Insertion | $n^2$ | Y | Y |
| Selection | $n^2$ | Y | N |
| Merge | $n \log n$ | N | Y |
| Quicksort | $n^2$ | Y | N |

## What's next

Standard sorting algorithms are a core foundation for all advanced algorithm design topics in CIE 9618. Understanding their complexity and properties will help you select the right algorithm for any problem, which is a key skill for Paper 2. You will apply this knowledge when writing pseudocode for sorting problems, analyzing efficiency of more complex algorithms, and solving mixed searching and sorting problems in your exam preparation.

- [Standard Searching Algorithms](https://www.owlsprep.com/study/cie-9618-u9-standard-searching-algorithms/)
- [Algorithm tracing](https://www.owlsprep.com/study/cie-9618-u9-algorithm-tracing/)
- [Data types & structures](https://www.owlsprep.com/study/cie-9618-u10-overview/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u9-standard-sorting-algorithms/