Skills101

AdvancedData Structures & Algorithms · Lesson 18 of 20 · Updated ·

Counting Sort, Stable Sorting and Custom Sort Orders

Comparison sorts (merge sort, quick sort, the built-in sort) can never beat O(n log n) in general. But when the values are small whole numbers — marks out of 100, ages, letters — you can skip comparisons entirely and sort in O(n + k), where k is the largest value. That is counting sort.

The second half of this lesson covers something you will use far more often: sorting by your own rule, such as "highest marks first, and by name when marks are equal".

1. Counting sort

Count how many times each value appears, then write the values out in order.

Counting sort of 4 2 2 8 3 3 1: the count array has count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1, and writing the values out in order gives 1 2 2 3 3 4 8

def counting_sort(a, k):
    """a holds whole numbers from 0 to k."""
    count = [0] * (k + 1)
    for x in a:
        count[x] += 1
    out = []
    for v in range(k + 1):
        out.extend([v] * count[v])
    return out

print(counting_sort([4, 2, 2, 8, 3, 3, 1], 8))
marks = [72, 95, 72, 40, 95, 88]
print(counting_sort(marks, 100))
[1, 2, 2, 3, 3, 4, 8]
[40, 72, 72, 88, 95, 95]
  • Time: O(n + k). Space: O(k) for the count array.
  • Use it when k is small compared with what n log n would cost — marks (k = 100), ages (k ≈ 120), lowercase letters (k = 26).
  • Don't use it when values are huge (up to 10⁹): the count array would be enormous.

The same counting idea answers many questions directly, without sorting: "is this string an anagram of that one?", "which value appears most often?", "sort a string's letters".

2. What "stable" means

A sort is stable if items with equal keys stay in their original order.

Students in input order Asha 85, Vikram 92, Ravi 85, Meena 78 sorted by marks high first gives Vikram 92, Asha 85, Ravi 85, Meena 78: Asha stays before Ravi because a stable sort keeps the order of equal keys

Why it matters: you can sort by several keys in steps. Sort by name first, then (stably) by marks — students with the same marks stay in name order. Python's sorted() / list.sort() and Java's sort for objects (Collections.sort, Arrays.sort on objects) are all stable.

3. Custom sort order in Python: the key function

sorted() takes a key: a function that turns each item into the value to compare. Return a tuple to sort by several things — Python compares tuples item by item.

students = [("Asha", 85), ("Vikram", 92), ("Ravi", 85), ("Meena", 78)]

by_marks = sorted(students, key=lambda s: s[1], reverse=True)
print(by_marks)

# marks high to low, then name A to Z when marks are equal
ranked = sorted(students, key=lambda s: (-s[1], s[0]))
print(ranked)

words = ["pear", "fig", "kiwi", "apple", "date"]
print(sorted(words, key=len))                    # equal lengths keep their input order
print(sorted(words, key=lambda w: (len(w), w)))  # equal lengths sorted A to Z
[('Vikram', 92), ('Asha', 85), ('Ravi', 85), ('Meena', 78)]
[('Vikram', 92), ('Asha', 85), ('Ravi', 85), ('Meena', 78)]
['fig', 'pear', 'kiwi', 'date', 'apple']
['fig', 'date', 'kiwi', 'pear', 'apple']
  • -s[1] sorts numbers in descending order while the name still sorts ascending.
  • reverse=True reverses the whole order; it keeps the sort stable.

4. Custom sort order in Java: Comparator

In Java you pass a Comparator. Build it with Comparator.comparing(...), then chain .reversed() and .thenComparing(...).

import java.util.*;

public class Main {
    record Student(String name, int marks) {}

    public static void main(String[] args) {
        List<Student> list = new ArrayList<>(List.of(
            new Student("Asha", 85), new Student("Vikram", 92),
            new Student("Ravi", 85), new Student("Meena", 78)));

        list.sort(Comparator.comparingInt(Student::marks).reversed()
                            .thenComparing(Student::name));
        for (Student s : list) System.out.println(s.name() + " " + s.marks());

        Integer[] nums = {5, 1, 4};
        Arrays.sort(nums, Collections.reverseOrder());
        System.out.println(Arrays.toString(nums));
    }
}
Vikram 92
Asha 85
Ravi 85
Meena 78
[5, 4, 1]

Watch out: Collections.reverseOrder() works on Integer[], not on a primitive int[]. For int[], sort ascending and read it backwards.

Never write a comparator as a - b for large numbers: 2_000_000_000 - (-2_000_000_000) overflows and gives the wrong sign. Use Integer.compare(a, b) or Comparator.comparingInt.

5. A classic: sort by frequency

"Sort the characters by how often they appear, most frequent first; break ties alphabetically." Count first, then sort with a key.

from collections import Counter

def frequency_sort(s):
    c = Counter(s)
    order = sorted(c, key=lambda ch: (-c[ch], ch))
    return "".join(ch * c[ch] for ch in order)

print(frequency_sort("programming"))
ggmmrrainop

Common mistakes

  • Using counting sort on values up to 10⁹ — the count array alone would need gigabytes.
  • Expecting sorted(..., key=len) to also sort words of equal length alphabetically. It keeps their original order; add the word itself to the key.
  • a - b comparators that overflow in Java.
  • Calling Arrays.sort(intArray, Collections.reverseOrder()) — it doesn't compile for primitives.

Quick recap

  • Counting sort: count each value, write them out in order — O(n + k), only for small integer ranges.
  • A stable sort keeps equal items in their input order; Python's sort and Java's object sort are stable.
  • Python: sorted(items, key=lambda x: (-x.score, x.name)).
  • Java: Comparator.comparingInt(...).reversed().thenComparing(...), and Integer.compare instead of subtraction.

Practice what you learned

📝 Quiz: Counting Sort and Custom Sorting5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →