Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 77 · CS Fundamentals Interview Questions

Sorting and Searching Catalog: Shell, Counting, Radix, Bucket, Ternary and Fibonacci

Compare Shell, counting, radix, bucket, ternary and Fibonacci search with runnable Python, a complexity and stability table, and answers to common follow-ups.

Everyone knows quicksort and binary search. Interviews often go one level further: "sort a million numbers in the range 0 to 100", "sort by last digit then by first", "find the peak of a function", "what is the fastest way to sort strings of equal length?" The answers come from the less famous algorithms in this lesson.

All examples run in Python in the page. For the main algorithms see Sorting and Binary search; the questions on array patterns are in Array and String Patterns.

Two families of sorts

Comparison sorts Need at least n log n comparisons.
Non-comparison sorts Use the key itself. Can reach O(n).

Counting, radix and bucket sort beat n log n only under assumptions about the keys.

1 / 2

Why is O(n log n) the limit for comparison sorts?

Short answer: a comparison sort decides the order by asking yes/no questions ("is a[i] < a[j]?"). There are n! possible orders, and each answer at best halves the possibilities, so you need at least log2(n!) comparisons, which is Θ(n log n).

That is a lower bound for algorithms that only compare. It says nothing about sorts that read the key itself, such as counting or radix sort. When someone asks "can you sort faster than n log n?", the right answer is "yes, if the keys are integers in a limited range, because then I do not need comparisons".

Shell sort: insertion sort with big steps

Insertion sort is slow because an element may need to move many places, one swap at a time. Shell sort first sorts elements that are gap apart (gap 4, then 2, then 1), so elements travel long distances early. The last pass with gap 1 is a normal insertion sort, but on an almost sorted array, where insertion sort is near O(n).

The running time depends on the gap sequence: halving gaps (n/2, n/4, ... 1) gives O(n²) worst case, while better sequences (Sedgewick, Ciura) are much faster in practice. It sorts in place and is not stable.

Python Shell sort with halving gaps

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting sort: when keys are small integers

Q: How do you sort a million exam scores between 0 and 100 in linear time? Count how many times each value occurs, then rebuild the output. With k possible values it takes O(n + k) time and O(n + k) space. It is not comparison-based, so it is not bound by n log n.

To make it stable (equal keys keep their input order, which radix sort needs), turn the counts into prefix sums (the last output position for each value) and place elements walking the input from right to left.

Python Stable counting sort with prefix sums

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The trap: if k is huge (say 10 billion possible values for 100 numbers), counting sort uses far more memory and time than a comparison sort. State the condition k = O(n).

Radix sort: one digit at a time

Radix sort sorts integers (or fixed-length strings) by one digit at a time, using a stable sort for each pass. LSD (least significant digit first) starts from the last digit; because each pass is stable, the earlier, less significant order survives as tie-breaking, and after the most significant digit the array is fully sorted. With d digits in base b the cost is O(d · (n + b)).

Python LSD radix sort with a stable bucket pass

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Radix sort handles non-negative integers as written; for negative numbers, sort positives and negatives separately or offset by the minimum. For variable-length strings, use MSD radix sort or pad them.

Bucket sort: uniform data

Bucket sort splits the range into n buckets, drops each element into its bucket, sorts each bucket (usually with insertion sort), and concatenates. If the input is spread evenly (for example floats in [0, 1)), each bucket holds about one element and the total is O(n) on average. If everything lands in one bucket it degrades to the cost of the inner sort, up to O(n²). It needs O(n) extra space and is stable if the inner sort is.

Python Bucket sort for floats in [0, 1)

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity and stability at a glance

Algorithm Best Average Worst Extra space Stable
Insertion O(n) O(n²) O(n²) O(1) Yes
Shell (halving gaps) O(n log n) depends on gaps O(n²) O(1) No
Merge O(n log n) O(n log n) O(n log n) O(n) Yes
Quick O(n log n) O(n log n) O(n²) O(log n) No
Heap O(n log n) O(n log n) O(n log n) O(1) No
Counting O(n + k) O(n + k) O(n + k) O(n + k) Yes (right-to-left)
Radix (LSD) O(d(n + b)) O(d(n + b)) O(d(n + b)) O(n + b) Yes
Bucket O(n + k) O(n) uniform O(n²) O(n + k) Yes (stable inner sort)

Python's sorted is Timsort: stable, O(n) on already sorted runs and O(n log n) worst case, which is why you rarely hand-write a sort in production.

Ternary search: finding a peak

Binary search needs a sorted array. Ternary search looks for the maximum (or minimum) of a unimodal function, one that strictly increases and then strictly decreases. Evaluate two interior points m1 < m2; if f(m1) < f(m2) the peak is not to the left of m1, otherwise it is not to the right of m2. Each step discards a third of the range, so it needs O(log n) steps (base 3/2). On integers, plateaus break the logic; with equal neighbors you cannot decide which side to drop.

Python Ternary search for the peak of a unimodal array

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a sorted array, plain binary search does the same job with fewer comparisons (log2 versus about 2·log3 evaluations), so ternary search is for unimodal functions, not for sorted lookup. A peak in a "mountain" array can also be found with binary search on the slope: compare a[mid] with a[mid + 1].

Fibonacci search searches a sorted array using Fibonacci numbers to choose the probe position instead of the midpoint. It uses only addition and subtraction (no division), and it accesses elements near each other, which once mattered for tape drives and caches. It is still O(log n). In interviews it is a "know that it exists" topic: the idea is to find the smallest Fibonacci number F(k) >= n, probe at offset + F(k-2), and shrink the range to a sub-interval of size F(k-1) or F(k-2).

Python Fibonacci search in a sorted array

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which would you pick?

  • Integers in a small known range, need linear time: counting sort.
  • Many fixed-width integers or strings: radix sort.
  • Floats spread evenly over a range: bucket sort.
  • General data, stability required: merge sort / Timsort.
  • General data, memory tight, no stability needed: heap sort or in-place quicksort with a good pivot.
  • Nearly sorted data: insertion sort (or Timsort, which exploits runs).
  • Peak of a unimodal function: ternary search (or binary search on the slope).

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Why can counting sort run in O(n + k) even though comparison sorts need at least n log n?

    The n log n bound is for algorithms that learn the order only by comparing. Counting sort reads the key value directly, at the cost of memory proportional to the key range k.
  2. 2. In LSD radix sort, what must be true of the per-digit sort?

    A stable pass preserves the order produced by the earlier, less significant digits, so ties on the current digit are broken correctly.
  3. 3. Bucket sort is O(n) on average only if...

    With evenly spread data each bucket is tiny. If most elements fall into one bucket, the work is dominated by sorting that bucket.
  4. 4. You must find the maximum of a function that increases and then decreases. Which approach fits best?

    Unimodal functions can be searched by comparing two interior points and discarding the third that cannot contain the peak.
  5. 5. Which of these sorts is NOT stable in its usual form?

    Shell sort moves equal elements across gaps, so their relative order can change. Merge, insertion and the right-to-left counting sort preserve it.

Summary

  • Comparison sorts cannot beat Θ(n log n); counting, radix and bucket sort avoid comparisons by exploiting the keys.
  • Counting sort needs a small key range k; radix sort applies a stable pass per digit; bucket sort relies on uniform data.
  • Shell sort is a gapped insertion sort, in place and unstable; its speed depends on the gap sequence.
  • Stability and extra space are part of every sorting answer; Timsort is the practical default.
  • Ternary search finds the peak of a unimodal function; Fibonacci search is a O(log n) search on sorted data that avoids division.

Next: Trees and Graphs Questions.