Sorting

Sorting means putting values in order, such as smallest to largest. In this topic, O(n²) and O(n log n) describe how the number of steps grows with the number of values n (see Basics and maths); log n here means how many times you can halve n, about 20 for a million values. It comes up in two ways in tester interviews. Sometimes you are asked to write a sort yourself, usually bubble sort, sometimes merge sort or quick sort, to show you understand loops and cost. More often, sorting is the first step that makes another problem easy: merging intervals, counting platforms, grouping anagrams or ranking words by frequency.

The simple sorts: O(n²)

Bubble sort walks the list and swaps neighbours that are out of order; after each pass the largest remaining value has moved to the end. Stop when a pass makes no swap. Selection sort finds the smallest remaining value and swaps it to the front. Insertion sort keeps the left part sorted and inserts the next value by shifting larger values right. For 5, 2, 9, 1, 5 insertion sort goes: 2 moves before 5; 9 stays; 1 moves to the front; the second 5 stops after the first 5.

All three take O(n²) time in the worst case. That is fine for a few thousand values and far too slow for 100,000. Insertion sort does very little work on a list that is already almost sorted, which is why real library sorts use it for small pieces.

The fast sorts: O(n log n)

Merge sort splits the list in half, sorts each half, and merges the two sorted halves by repeatedly taking the smaller front value. Sorting 5, 2, 3, 1: the pairs become 2, 5 and 1, 3, and merging them takes 1, 2, 3, 5. There are about log n levels of splitting and each level does n work, so it is O(n log n) on every input. It needs O(n) extra memory, and it is stable: equal values keep their original order.

Quick sort picks a pivot (the value it splits around), moves smaller values to its left and larger values to its right, and sorts both sides. It is O(n log n) on average and works in place (inside the same list, without a big second copy), but a bad pivot makes it O(n²): always picking the first value is slow on already sorted input, and a split that puts every value equal to the pivot on one side is slow when all values are equal. A random or middle pivot and a three-way split fix both.

When values come from a small range, counting sort is faster still: count how often each value occurs, then write them back in order. Sorting the characters of an ASCII string is the classic case.

Library sorts and your own rules

In real code, use the library. In Java, Arrays.sort on an array of plain numbers (primitives) uses a dual-pivot quick sort, while sorting objects uses a stable merge sort (the documentation says it is adapted from TimSort), and Collections.sort is guaranteed to be stable too. In Python, sorted() and list.sort() are guaranteed to be stable. All of them are O(n log n).

To sort by your own rule, give Java a comparator (a small function that says which of two values comes first) and give Python a key function (a function that returns the value to sort by). A common task is "sort words by count, highest first, and alphabetically when counts are equal". The program below does that and also shows insertion sort written by hand.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] nums = {5, 2, 9, 1, 5};
        for (int i = 1; i < nums.length; i++) {
            int value = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > value) {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = value;
        }
        System.out.println(Arrays.toString(nums));

        Map<String, Integer> counts = Map.of("cat", 2, "the", 3, "bat", 2, "hat", 1);
        List<String> words = new ArrayList<>(counts.keySet());
        words.sort(Comparator.comparing((String w) -> -counts.get(w)).thenComparing(w -> w));
        System.out.println(words);
    }
}

[1, 2, 5, 5, 9]
[the, bat, cat, hat]

nums = [5, 2, 9, 1, 5]
for i in range(1, len(nums)):
    value = nums[i]
    j = i - 1
    while j >= 0 and nums[j] > value:
        nums[j + 1] = nums[j]
        j -= 1
    nums[j + 1] = value
print(nums)

counts = {"cat": 2, "the": 3, "bat": 2, "hat": 1}
words = sorted(counts, key=lambda w: (-counts[w], w))
print(words)

[1, 2, 5, 5, 9]
['the', 'bat', 'cat', 'hat']

The Python key returns a pair: minus the count (so higher counts come first) and the word (so ties are alphabetical). The Java comparator does the same in two steps.

Problems that become easy after sorting

• Merge overlapping intervals: sorted by start, overlapping intervals sit next to each other, so one sweep merges them.
• Minimum platforms or meeting rooms: sort arrival and departure times separately and sweep both like a merge, counting how many are open at once.
• Anagrams: two words are anagrams exactly when their sorted letters are equal.
• Duplicates without extra memory: after sorting, equal values are neighbours.

How to answer in an interview

If you are asked to write a sort, say which one and why, trace it on a tiny example with a duplicate value, and give its cost. If sorting is a step in a bigger problem, say so early ("sort by start time, then one sweep") and give the total: O(n log n) for the sort plus O(n) for the sweep. Mention a hash-based O(n) answer when one exists.

Common mistakes

• Forgetting the tie-break in a custom sort, so equal counts come out in a random order.
• A bubble sort inner loop that reads one position past the end.
• Using a simple O(n²) sort on 100,000 values.
• Picking the first value as the quick sort pivot on sorted input.
• Not knowing what "stable" means: equal values keep their order, which matters when you sort by salary a list already sorted by name.

Recap

Know the three simple sorts (O(n²)), merge sort (O(n log n), stable, O(n) extra space) and quick sort (O(n log n) on average, O(n²) at worst). In real problems, sorting first often turns a hard question into one sweep.