TRT
Sign in

Core · Module 8 · Lesson 4 of 5

Counting and radix sort

No sort that only compares elements can beat about n log n comparisons. Counting sort and radix sort don't compare at all: they use the keys as numbers, and sort integers in linear time.

Pro — members onlyAbout 14 minutes

By the end you can

  • Explain why comparison sorts need about n log₂ n comparisons in the worst case
  • Sort integers from a small range with counting sort in O(n + k), stably
  • Sort fixed-width keys with least-significant-digit radix sort, and explain why each pass must be stable

Builds on Quick sort and partitioning.

01 · A question first

No algorithm that sorts by comparing elements can use fewer than about n log₂ n comparisons in the worst case. Yet sorting a million exam scores between 0 and 100 can be done in a couple of passes over the data. Which rule does that break?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • The comparison barrier
  • Counting sort
  • Radix sort
  • Bucket sort
  • When to use them
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · easy · LeetCodeValid anagramDecide whether two strings are anagrams by counting letters instead of sorting, in O(n) time.Practice · medium · LeetCodeMaximum gapFind the largest difference between consecutive values in sorted order, in linear time, without a comparison sort.

Asked in interviews

Something wrong with this lesson? Report a problem