Algorithmsmedium

Counting sort: when can it be faster than O(n log n) sorting?

Answer

Counting sort is good when keys are integers in a small range 0..k. It runs in O(n + k) by counting occurrences and building the output, and it can be stable (useful as a building block for radix sort).

Related questions

Algorithms

Heap sort: what are its time complexity, space complexity, and stability?

#heapsort#sorting#complexity

Algorithms

Quickselect: what is it used for and what is its expected complexity?

#quickselect#selection#partition

Algorithms

What is a monotonic queue and how does it solve sliding window max in O(n)?

#deque#monotonic-queue#sliding-window

Algorithms

Kruskal vs Prim for MST — how do they differ?

#mst#kruskal#prim

Algorithms

Randomized pivot in QuickSort/Quickselect — why does it help?

#randomization#quicksort#quickselect

Algorithms

What is a monotonic stack and what kind of problems does it solve?

#stack#monotonic-stack#next-greater