Standard sorting algorithms

Computer Science· Unit 9: Algorithm design & problem solving· 6 min read

1. Simple Quadratic-Time Sorting Algorithms★★☆☆☆⏱ 20 min

🚫 No Calculator

📘 Definition

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 ∣ 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 ∣ 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 ∣ 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]$

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.

2. Merge Sort: Divide-and-Conquer Sorting★★★☆☆⏱ 25 min

🚫 No Calculator

📘 Definition

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]$

3. Quicksort: Partition-Based Divide-and-Conquer Sorting★★★★☆⏱ 25 min

🚫 No Calculator

📘 Definition

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.

4. Comparing Sorting Algorithm Properties★★★☆☆⏱ 20 min

🚫 No Calculator

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 lo g n)$	$O (n lo g n)$	$O (n lo g n)$	No	Yes
Quicksort	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$	Yes	No

✓ Quick check

Check your understanding of core properties:

Which algorithm always has $O (n lo g n)$ worst-case time complexity?
- Bubble sort
- Merge sort
- Quicksort
- Insertion sort
Reveal answer
1 —
Correct! Merge sort always splits the input into equal halves, so it always has $O (n lo g n)$ time regardless of input order.
Which of these algorithms is NOT in-place?
- Quicksort
- Insertion sort
- Merge sort
- Selection sort
Reveal answer
2 —
Correct! Standard merge sort requires extra $O (n)$ memory to store temporary merged subarrays.

5. Common Pitfalls

Wrong move:

Claiming quicksort is always $O (n lo g n)$ time

Why:

Quicksort degrades to $O (n^{2})$ time with poor pivot selection on sorted/reverse-sorted input

Correct move:

State that average time is $O (n lo g n)$ and worst-case time is $O (n^{2})$ for quicksort

Wrong move:

Forgetting that standard merge sort is not in-place

Why:

This is a common exam question that tests knowledge of core algorithm properties

Correct move:

Remember merge sort requires $O (n)$ extra memory, so it is not an in-place algorithm

Wrong move:

Counting the wrong number of passes for bubble sort

Why:

A common mistake is counting individual swaps as passes, leading to lost marks

Correct move:

A full pass processes all unsorted elements, so n elements need at most n-1 passes

Wrong move:

Claiming all in-place sorting algorithms are stable

Why:

Stability depends on swap implementation, not whether sorting is in-place

Correct move:

Memorize that selection sort and quicksort are unstable, bubble, insertion and merge are stable

Wrong move:

Merging before splitting recursively in merge sort

Why:

Many students mix up the order of operations for divide-and-conquer algorithms

Correct move:

Split the array first, recursively sort each half, then merge the sorted halves

6. Quick Reference Cheatsheet

Algorithm	Worst Time	In-place?	Stable?
Bubble	$n^{2}$	Y	Y
Insertion	$n^{2}$	Y	Y
Selection	$n^{2}$	Y	N
Merge	$n lo g n$	N	Y
Quicksort	$n^{2}$	Y	N

7. Frequently Asked

Which sorting algorithms do I need to memorize for 9618?

CIE 9618 requires full knowledge of 5 standard sorting algorithms: bubble sort, insertion sort, selection sort, merge sort and quicksort. You need to be able to trace their execution, compare properties, and write/complete pseudocode for them.

Do I need to memorize time complexity values for the exam?

Yes, you are expected to remember best, average and worst case time complexity, space complexity, and other properties for all 5 standard sorting algorithms.

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2022 · 2
Trace bubble sort execution on input
2023 · 2
Compare quicksort vs merge sort properties
2024 · 2
Identify stable sorting algorithms

Going deeper

syllabusOfficial CIE 9618 SyllabusSyllabus page 42 reference

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.