C++UCS301
Sorting AlgorithmsC++17

Sorting Foundations

Sorting algorithms are compared by time, extra space, stability, adaptiveness, and whether they operate in-place.

What to understand

  • Internal versus external sorting
  • Stable versus unstable
  • In-place algorithms
  • Comparison lower bound

Remember this

  1. 1Comparison sorts need Ω(n log n) comparisons in general
  2. 2Stable sorting preserves equal-key order
  3. 3External sorting minimises disk I/O

Detailed notes

Sorting establishes an order that simplifies searching, grouping, deduplication, merging, and presentation. Comparison sorts learn order only through comparisons; decision-tree reasoning gives them a general Ω(n log n) lower bound.

Stability preserves the input order of equal keys. In-place usually means O(1) or logarithmic auxiliary storage, adaptiveness rewards existing order, and external algorithms optimise transfers when data does not fit RAM.

How it works

  1. 1Define the key and comparator.
  2. 2Determine whether equal-key order matters.
  3. 3Compare input size, key range, and available memory.
  4. 4Choose internal or external processing from storage constraints.

Where it is used

  • Preparing data for binary search
  • Grouping records and producing reports
  • Canonical ordering for comparison and deduplication

Common mistakes

  • Assuming in-place implies stable
  • Using subtraction as a comparator and overflowing
  • Ignoring I/O cost for data larger than memory

Implementation perspective

This is primarily a conceptual or selection topic. Use the linked implementation topics in this section to see the invariant expressed in C++.

Exam & viva

Open a prompt when you are ready to check your answer.