# Counting Sort, Stable Sorting and Custom Sort Orders

Source: https://skills101.in/learn/dsa/dsa-counting-sort-custom-sorting — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-17.

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](https://skills101.in/learn-img/dsa/counting-sort.svg)

```python
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))
```

```text
[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](https://skills101.in/learn-img/dsa/stable-sort.svg)

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.

```python
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
```

```text
[('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(...)`.

```java
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));
    }
}
```

```text
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.

```python
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"))
```

```text
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 quiz and free certificate: https://skills101.in/learn/dsa/dsa-counting-sort-custom-sorting