What does a sorting algorithm do?
The key idea
A sorting algorithm rearranges items according to a defined comparison rule. Before choosing a method, specify the key, direction and treatment of equal values. Sorting numbers ascending is simpler to describe than sorting records with several possible keys.
For example, a list of course tasks could be sorted by deadline, while equal deadlines retain their original order. That extra requirement affects which behaviour is acceptable.
Trace insertion sort
Start with 8, 3, 5. Treat the first item as a sorted prefix. Insert 3 into that prefix, giving 3, 8, 5. Then insert 5 between 3 and 8, giving 3, 5, 8.
| Stage | Sorted prefix | Remaining items |
|---|---|---|
| Start | 8 | 3, 5 |
| Insert 3 | 3, 8 | 5 |
| Insert 5 | 3, 5, 8 | None |
The useful invariant is that the processed prefix is sorted. The next insertion extends that property by one item.
What is stability?
A stable sort preserves the relative order of items that compare equal. Suppose tasks A and B have the same deadline and A originally appears first. A stable deadline sort keeps A before B.
Stability does not mean “the algorithm always works.” It is a specific property of equal-key ordering. An unstable algorithm can still produce a correctly sorted sequence when equal-key order does not matter.
Compare typical properties carefully
| Algorithm | Typical worst-case time | A useful observation |
|---|---|---|
| Insertion sort | O(n squared) | Can suit small or nearly sorted inputs |
| Standard merge sort | O(n log n) | Common array implementations use extra storage |
| Heap sort | O(n log n) | Typical in-place version is not stable |
| Basic quicksort variants | O(n squared) | Pivot choices affect behaviour; expected performance can be better |
Implementation details matter. Do not transfer every property of a textbook version to every library function with a related name.
Include the comparison rule
If records have equal primary keys, decide whether to preserve input order or compare a second key. Make the comparator consistent. A rule that contradicts itself can invalidate the assumptions of a sorting routine.
For strings, ask whether the task needs a simple code-unit order or language-aware collation. Those are different requirements. Define the intended ordering before treating one output as correct.
Test more than a random list
Use an already sorted list, reverse order, repeated values, one element and an empty collection. For records, include equal keys and inspect their relative order if stability is required.
After sorting, check both order and preservation: every original item should still be present with the same multiplicity. A sorted output that loses a repeated item is incorrect.
Gammal Tech's Algorithms course follows Data Structures. Use these checks to compare methods by their contract and workload, rather than by which implementation has the fewest lines.
References and course details
Use these references for further study. The examples and exercises in this article are educational; consult the catalogue for course details.