Radix Sort: Complete Sorting Algorithm Guide

1. Introduction and Core Concepts

Radix sort is a non-comparative integer sorting algorithm that defies the conventional wisdom that sorting requires comparing elements against each other. Instead of directly comparing values, radix sort distributes elements into buckets according to their individual digits or radix positions, processing numbers digit by digit. This approach allows it to achieve linear time complexity for certain types of data, making it one of the most efficient sorting algorithms when its preconditions are met.

The term "radix" refers to the base of a number system. In decimal, the radix is 10; in binary, it is 2; and in hexadecimal, it is 16. Radix sort works by grouping keys by the individual digits which share the same significant position and value. Unlike comparison-based algorithms such as quicksort or mergesort, which have a theoretical lower bound of O(n log n), radix sort can sort in O(d * (n + k)) time, where d is the number of digits, n is the number of elements, and k is the range of each digit. When d is small and k is not significantly larger than n, this is effectively linear.

Understanding radix sort matters because it challenges the assumption that O(n log n) is the fastest possible sorting time and demonstrates how exploiting the structure of data can lead to dramatic performance gains. It is a classic example of a distribution sort and is closely related to bucket sort and counting sort. In fact, counting sort is most often used as the stable subroutine that makes radix sort work. For computer science students and professionals, mastering radix sort provides insight into stable sorting, digit-based processing, and the trade-offs between time, space, and data constraints.

Why Non-Comparative Sorting Matters

Comparison sorts make no assumptions about the data; they only need a comparator function. This generality comes at a cost: the Ω(n log n) lower bound proven by decision tree analysis. Non-comparative sorts like radix sort, counting sort, and bucket sort bypass this bound by making assumptions about the keys — for example, that they are integers in a bounded range, fixed-length strings, or binary representations. When those assumptions hold, they can be substantially faster.

Radix sort is particularly powerful for sorting large collections of integers, fixed-length strings, or any data that can be lexicographically ordered by components. Modern systems that sort millions of 32-bit or 64-bit integers, such as database engines, graphics pipelines, and high-frequency trading platforms, often rely on radix sort variants for their predictable, linear performance and cache-friendly behavior.

Key Properties at a Glance

Radix sort is stable, meaning elements with equal keys retain their relative order. Stability is not just a theoretical property; it is essential for the correctness of the algorithm itself, as later passes must preserve the ordering established by earlier passes. It is also an out-of-place algorithm in its most common implementation, requiring auxiliary space for buckets or counting arrays. While in-place variants exist, they are complex and rarely used in practice.

The algorithm comes in two primary flavors: Least Significant Digit (LSD) and Most Significant Digit (MSD). LSD radix sort starts from the rightmost digit and proceeds left, while MSD starts from the leftmost digit and recursively sorts buckets. Both are correct, but they have different performance characteristics, implementation complexity, and use cases, which we will explore in detail.

2. How It Works

At its core, radix sort works by repeatedly sorting the input by each digit position, from least significant to most significant or vice versa, using a stable sorting algorithm as a subroutine. The stability guarantee ensures that if two numbers have the same digit at the current position, their order determined by previous passes is preserved. After processing all digit positions, the entire array becomes sorted.

Consider decimal numbers. In the first pass, numbers are grouped by their units digit (0-9). In the second pass, they are grouped by their tens digit, but within each tens bucket, the order established by the units digit is maintained. This continues for hundreds, thousands, and so on. After d passes, where d is the maximum number of digits, the list is fully sorted. This is the LSD approach, and it is the most commonly implemented because it is iterative and straightforward.

The choice of stable subroutine is critical. Counting sort is ideal because it sorts by a single digit in O(n + k) time, where k is the radix (10 for decimal, 256 for byte-wise radix). Since k is typically small and constant, each pass is linear. Bucket sort can also be used, but counting sort is more efficient for digit ranges.

LSD vs. MSD Radix Sort

LSD radix sort processes digits from right to left. It always performs exactly d passes, where d is the number of digits in the longest number. It is simple to implement iteratively, requires no recursion, and is excellent for fixed-length keys like 32-bit integers. Its main drawback is that it must process all digits even if the most significant digits alone would be sufficient to distinguish many numbers.

MSD radix sort processes digits from left to left, analogous to how humans sort words alphabetically. It partitions the array into buckets based on the most significant digit, then recursively sorts each bucket by the next digit. MSD can be faster when keys have variable length or when early digits provide high discrimination, because it can stop recursing once a bucket contains a single element. However, it requires recursion or an explicit stack, careful handling of variable-length keys, and more complex bucket management.

The Role of Stability

To illustrate why stability is non-negotiable, imagine sorting [170, 045, 075, 090, 002, 024, 802, 066] by LSD. After sorting by the units digit, the order is [170, 090, 002, 802, 024, 045, 075, 066]. Notice 170 comes before 090 because both end in 0 and 170 appeared first originally. When we next sort by the tens digit, 802 (0 in tens place) must remain before 002 (0 in tens place) if they were previously ordered. If the subroutine were unstable, this relative order could be destroyed, and the final result would be incorrect. This dependency is why counting sort, which is stable when implemented correctly by iterating backwards during placement, is the perfect partner.

The base or radix chosen also affects performance. While base 10 is intuitive for explanation, computers operate in binary. Using a radix of 256 (2^8) means we process one byte at a time, so a 32-bit integer requires only 4 passes instead of 10 decimal passes. Using radix 65536 (2^16) requires only 2 passes but needs a count array of size 65536. This trade-off between number of passes and auxiliary space is a key optimization lever.

3. Implementation

Implementing radix sort correctly requires attention to stability, handling of edge cases such as empty arrays, negative numbers, and variable-length keys, and efficient memory usage. Below are four production-quality Python implementations covering the most common scenarios.

LSD Radix Sort with Counting Sort Subroutine

The following implementation is the canonical LSD radix sort for non-negative integers using base 10. It isolates the counting sort logic for clarity and ensures stability by traversing the input array backwards when building the output.

def counting_sort_by_digit(arr, exp):
    """
    Stable counting sort of arr by digit at exponent exp.
    exp = 1 -> units, 10 -> tens, 100 -> hundreds, etc.
    """
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # decimal radix

    # Count occurrences of each digit
    for i in range(n):
        digit = (arr[i] // exp) % 10
        count[digit] += 1

    # Transform count to positions: count[i] now contains
    # actual position of this digit in output
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Build output array backwards to maintain stability
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1

    # Copy back to original array
    for i in range(n):
        arr[i] = output[i]

def radix_sort_lsd(arr):
    """LSD radix sort for non-negative integers (base 10)."""
    if not arr or len(arr) <= 1:
        return arr

    max_val = max(arr)
    exp = 1
    # Process every digit while there are digits left
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

# Example usage
data = [170, 45, 75, 90, 802, 24, 2, 66]
print(radix_sort_lsd(data))  # [2, 24, 45, 66, 75, 90, 170, 802]

Optimized Binary Radix Sort (Base 256)

For performance-critical applications, processing one byte at a time is far more efficient than one decimal digit. This version sorts 32-bit integers in just 4 passes with a radix of 256. It uses bit shifting and masking instead of division and modulo.

def radix_sort_binary(arr):
    """LSD radix sort using base 256 (byte-wise) for 32-bit non-negative ints."""
    if not arr or len(arr) <= 1:
        return arr

    n = len(arr)
    # 4 passes for 32-bit integers (4 bytes * 8 bits)
    for shift in range(0, 32, 8):
        output = [0] * n
        count = [0] * 256  # radix = 256

        # Count byte occurrences
        for num in arr:
            byte_val = (num >> shift) & 0xFF
            count[byte_val] += 1

        # Prefix sum to get positions
        for i in range(1, 256):
            count[i] += count[i - 1]

        # Stable placement backwards
        for i in range(n - 1, -1, -1):
            byte_val = (arr[i] >> shift) & 0xFF
            count[byte_val] -= 1
            output[count[byte_val]] = arr[i]

        # Copy back
        for i in range(n):
            arr[i] = output[i]

    return arr

# Example: sorting large integers efficiently
import random
large_data = [random.randint(0, 2**32 - 1) for _ in range(10)]
print(radix_sort_binary(large_data.copy()))

Handling Negative Numbers and Edge Cases

Classic radix sort only handles non-negative integers. To support negatives, the standard technique is to partition the array into negative and non-negative parts, sort each separately, and then combine. Negatives require special handling because their order is reversed when sorting by absolute value.

def radix_sort_with_negatives(arr):
    """Full radix sort that correctly handles negative integers."""
    if not arr or len(arr) <= 1:
        return arr

    # Separate negatives and non-negatives
    negatives = [-x for x in arr if x < 0]
    positives = [x for x in arr if x >= 0]

    # Sort both partitions
    if positives:
        radix_sort_lsd(positives)
    if negatives:
        radix_sort_lsd(negatives)
        # Negatives sorted by absolute value are in reverse order
        # e.g., [-5, -2] -> abs [5,2] -> sorted [2,5] -> need [-5, -2]
        negatives = [-x for x in reversed(negatives)]

    return negatives + positives

# Example with mixed signs
mixed = [170, -45, 75, -90, -802, 24, 2, -66]
print(radix_sort_with_negatives(mixed))
# [-802, -90, -66, -45, 2, 24, 75, 170]

MSD Radix Sort for Variable-Length Strings

Radix sort is not limited to integers. MSD radix sort excels at sorting strings lexicographically, which is how dictionaries and file systems order names. This implementation recursively buckets strings by character position.

def msd_radix_sort_strings(arr, pos=0):
    """
    MSD radix sort for strings (lexicographic order).
    Handles variable-length strings correctly.
    """
    if len(arr) <= 1:
        return arr

    # Check if all strings are exhausted at this position
    if pos >= max(len(s) for s in arr):
        return arr

    buckets = {}
    for s in arr:
        # Use '' as sentinel for strings shorter than pos
        key = s[pos] if pos < len(s) else ''
        buckets.setdefault(key, []).append(s)

    result = []
    # '' (shorter strings) comes first lexicographically
    for key in sorted(buckets.keys()):
        bucket = buckets[key]
        if key == '':
            # Strings that ended are already sorted
            result.extend(bucket)
        else:
            # Recursively sort bucket by next character
            result.extend(msd_radix_sort_strings(bucket, pos + 1))
    return result

# Example: sorting filenames or words
words = ["apple", "app", "apricot", "banana", "bat", "batman"]
print(msd_radix_sort_strings(words))
# ['app', 'apple', 'apricot', 'banana', 'bat', 'batman']

4. Step-by-Step Example

Let us walk through a complete LSD radix sort execution on a concrete array to make the abstract process tangible. We will sort the array [170, 45, 75, 90, 802, 24, 2, 66] using base 10. The maximum value is 802, so we need three passes (units, tens, hundreds).

Initial array: [170, 45, 75, 90, 802, 24, 2, 66]. We will track the state after each digit pass, showing how stability preserves prior work.

Pass 1: Sort by Units Digit (exp = 1)

We extract the units digit for each number: 170→0, 45→5, 75→5, 90→0, 802→2, 24→4, 2→2, 66→6. Grouping by this digit using stable counting sort yields buckets: 0: [170, 90], 2: [802, 2], 4: [24], 5: [45, 75], 6: [66]. Concatenating buckets in order gives [170, 90, 802, 2, 24, 45, 75, 66]. Notice that 802 appears before 2 because it appeared first in the original array and both have digit 2; stability is preserved.

At this point, the array is sorted by the least significant digit only. It is not yet globally sorted, but any two numbers that differ only in the units place are now correctly ordered.

Pass 2: Sort by Tens Digit (exp = 10)

Now we sort the result of Pass 1 by the tens digit: 170→7, 90→9, 802→0, 2→0, 24→2, 45→4, 75→7, 66→6. Applying stable counting sort to the current array [170, 90, 802, 2, 24, 45, 75, 66] groups as: 0: [802, 2], 2: [24], 4: [45], 6: [66], 7: [170, 75], 9: [90]. The output is [802, 2, 24, 45, 66, 170, 75, 90].

Observe the bucket for digit 7: it contains [170, 75] in that order because 170 came before 75 in the input to this pass. This preservation ensures that within the same tens digit, numbers remain sorted by units. Similarly, [802, 2] retains its Pass 1 order.

Pass 3: Sort by Hundreds Digit (exp = 100)

Finally, we sort by the hundreds digit: 802→8, 2→0, 24→0, 45→0, 66→0, 170→1, 75→0, 90→0. Grouping the array [802, 2, 24, 45, 66, 170, 75, 90] yields: 0: [2, 24, 45, 66, 75, 90], 1: [170], 8: [802]. Concatenated, we get [2, 24, 45, 66, 75, 90, 170, 802], which is fully sorted.

Numbers with no hundreds digit are treated as having 0, so they correctly appear before 170 and 802. After three passes, every digit position has been considered, and the stability of each pass has ensured that the final order respects all digit positions from most to least significant. This walkthrough demonstrates why LSD radix sort works: each pass refines the ordering, and stability ensures refinement never undoes prior progress.

5. Complexity Analysis

Radix sort's performance is often misunderstood because it is not directly comparable to O(n log n) sorts without considering the parameters d and k. Its efficiency depends on the number of digits and the radix chosen, making analysis more nuanced than for comparison sorts.

Let n be the number of elements, d be the number of digits (or bytes) in the maximum element, and k be the radix (the range of each digit, e.g., 10 for decimal, 256 for base-256). Each pass of counting sort takes O(n + k) time to count, compute prefix sums, and place elements. With d passes, total time is O(d * (n + k)). If d is constant and k is O(n), this simplifies to O(n). For 32-bit integers with radix 256, d = 4 and k = 256, so time is O(4 * (n + 256)) = O(n).

Space complexity is O(n + k) for the output array and count array. The output array is O(n) and the count array is O(k). For base 10, this is O(n + 10) = O(n); for base 256, O(n + 256) = O(n). MSD radix sort can require additional space for recursion stack and buckets, worst-case O(n * d) in naive implementations, though optimized versions reuse buffers.

When Is It Truly Linear?

Radix sort is linear only when d and k are bounded. If you sort n numbers where each number can be up to n^2, then d = log_k(n^2) = 2 log_k n, so time becomes O(log_k n * (n + k)). If k is chosen as n, this is O(n log_n n) which is not linear in the traditional sense. In practice, for fixed-width data types like 32-bit ints, 64-bit ints, or fixed-length strings, d is constant, so linear time holds.

Another consideration is that radix sort's constant factors can be higher than quicksort's for small n due to multiple passes and auxiliary array allocations. Benchmarks typically show radix sort overtaking quicksort for n greater than a few thousand when sorting integers, but for n < 1000, the overhead may make it slower. Cache performance also matters: counting sort's scattered writes can cause cache misses if not optimized.

Best, Average, and Worst Cases Are Identical

Unlike quicksort, which degrades to O(n^2) on sorted or reverse-sorted input without randomization, radix sort's time is independent of input order. It always performs exactly d passes, each doing the same amount of work. This predictability is a major advantage in real-time systems where worst-case guarantees matter more than average-case speed. There is no pivot choice or branch misprediction based on data distribution; performance is deterministic.

6. Variations and Optimizations

While the textbook LSD radix sort is elegant, production implementations employ several optimizations and variants to handle diverse data types and maximize hardware efficiency.

American Flag Sort and In-Place Variants

American Flag Sort is an in-place variant of MSD radix sort that partitions the array into buckets by swapping elements, similar to quicksort's partition step, but based on digit value rather than pivot comparison. It avoids allocating a full auxiliary array, reducing space to O(k) for counts plus recursion stack. However, in-place distribution is more complex to implement stably and can be slower due to extra swaps. It is useful when memory is constrained, such as in embedded systems.

Another optimization is to use hybrid algorithms: for small buckets (e.g., fewer than 32 elements), switch to insertion sort, which has lower overhead and better cache locality for tiny arrays. This is analogous to how optimized quicksort switches to insertion sort for small subarrays.

Radix Choice and Adaptive Bases

Choosing the radix is a critical tuning parameter. A larger radix means fewer passes but larger count arrays and potentially more cache misses. For 64-bit integers, common choices are radix 256 (8 bits, 8 passes), radix 65536 (16 bits, 4 passes), and radix 2^11 = 2048 (11 bits, 6 passes). The optimal choice depends on n and cache size. Some adaptive implementations profile the data and choose radix dynamically: if n is small, use smaller radix to keep count array in L1 cache; if n is large, use larger radix to reduce passes.

For strings, radix is typically 256 (extended ASCII) or 65536 (Unicode). MSD string sort can also use a technique called "radix sort with cutoff" where it stops recursing when bucket size is small and uses quicksort for the remainder, combining the best of both worlds.

Handling Variable Length and Floating Point

Sorting variable-length strings with LSD is awkward because you must pad shorter strings. MSD handles this naturally by treating missing characters as smaller than any real character. For floating-point numbers, radix sort can be applied by reinterpreting the IEEE 754 bit pattern as integers with special handling for sign and exponent. Positive floats sort correctly as integers when interpreted as sign-magnitude, but negative floats need bit flipping. Libraries like Google's Highway and Intel's IPP include highly optimized radix sorts for floats that reinterpret bits and handle NaNs.

Parallel and GPU radix sort is another major variation. Because each counting pass can be parallelized via prefix sums (parallel scan), radix sort maps well to GPUs and multi-core CPUs. NVIDIA's CUB library and AMD's rocPRIM provide GPU radix sorts that can sort billions of keys per second by distributing counting and scattering across thousands of threads. These implementations use hierarchical counting and shared memory to minimize global memory traffic.

7. Real-World Applications

Radix sort is not just an academic curiosity; it powers critical infrastructure where sorting large volumes of structured keys must be fast and predictable.

Databases and Data Warehouses

Database engines frequently need to sort integers for index creation, join operations, and ORDER BY queries. When sorting primary keys, foreign keys, or timestamps that are 32- or 64-bit integers, radix sort can be 2-3x faster than quicksort. Columnar databases like ClickHouse and Apache Arrow use radix sort for sorting dictionary-encoded columns and for partitioning data during merges. Because database sorts often involve millions to billions of rows, the linear scaling of radix sort translates to significant latency and cost savings.

Networking and Systems Programming

Network routers and switches sort IP addresses, which are 32-bit (IPv4) or 128-bit (IPv6) integers, for routing table lookups, firewall rule matching, and packet classification. Radix sort's ability to sort IP addresses in 4 passes (for IPv4 with base 256) makes it ideal for building sorted routing tables quickly after updates. Similarly, operating system kernels sort process IDs, file descriptors, and memory addresses using radix sort during scheduling and garbage collection phases.

Web servers and load balancers sort log entries by timestamp or request ID for analytics and debugging. Since timestamps are integers (Unix epoch), radix sort provides stable, fast ordering that preserves the original log order for entries with identical timestamps, which is crucial for reconstructing request sequences.

Graphics, Scientific Computing, and Beyond

In computer graphics, radix sort is used to sort particles, triangles, or voxels by depth (z-order) or by Morton codes for spatial indexing. Real-time rendering of millions of particles requires sorting every frame at 60+ FPS, and GPU radix sort is often the only algorithm fast enough. Scientific simulations that use particle methods (e.g., smoothed-particle hydrodynamics) also rely on radix sort for neighbor searches.

Bioinformatics sorts DNA k-mers, which are fixed-length strings over alphabet {A,C,G,T} (radix 4), using radix sort to build suffix arrays and Burrows-Wheeler transforms for genome assembly. The small radix and fixed length make radix sort exceptionally efficient for this domain.

8. Comparison with Alternatives

Choosing a sorting algorithm requires understanding trade-offs in time complexity, space, stability, and data assumptions. Radix sort excels in specific niches but is not a universal replacement for comparison sorts.

Comparison sorts like quicksort, mergesort, and heapsort work for any comparable data with only a comparator function, making them general-purpose. Radix sort requires keys that can be decomposed into digits and a known radix, limiting it to integers, strings, and similar structured types. However, when applicable, it can be asymptotically faster.

When to Choose Which

Choose radix sort when you have many elements (n > 10,000) with fixed-width keys such as 32-bit ints, 64-bit timestamps, or short strings, and you need stable, predictable linear performance. It is the default choice for GPU sorting and for database systems sorting integer keys.

Choose quicksort or introsort (hybrid quicksort/heapsort used in most standard libraries) when you need a general-purpose, in-place sort for arbitrary objects with custom comparators and you cannot assume anything about key structure. Python's Timsort and C++'s std::sort are comparison sorts optimized for real-world data patterns.

Choose counting sort when k is very small (e.g., sorting ages 0-120, exam scores 0-100, or bytes 0-255) and you need O(n + k) with minimal passes. Radix sort actually uses counting sort internally, so counting sort is a special case of radix sort with d = 1.

Choose mergesort when you need a stable comparison sort that works well for linked lists, external sorting (data on disk), or when you need guaranteed O(n log n) without quicksort's worst-case risk. Mergesort is also highly parallelizable.

9. Common Mistakes and Best Practices

Even though radix sort is conceptually simple, implementation pitfalls can lead to incorrect results, poor performance, or subtle bugs that only appear with specific inputs.

Top Pitfalls to Avoid

1. Using an Unstable Subroutine: The most common mistake is implementing counting sort without preserving stability. If you iterate forward when placing elements into the output array, or if you use an unstable sort like quicksort for digit sorting, the final result will be incorrect. Always iterate backwards when distributing from the count array, or use the prefix-sum method that inherently maintains stability.

2. Ignoring Negative Numbers: Naively applying radix sort to arrays containing negatives will produce wrong order because the most significant bit or digit handling differs for negatives. Always partition negatives and positives, or bias the keys by adding an offset (e.g., add 2^31 to 32-bit signed ints to map them to unsigned range), then sort as unsigned.

3. Incorrect Digit Extraction: Using floating-point division or incorrect modulus for digit extraction can cause off-by-one errors, especially with large numbers or non-decimal radices. For base 10, use (num // exp) % 10; for base 256, use (num >> shift) & 0xFF. Test digit extraction in isolation before integrating.

4. Not Handling Variable-Length Keys: For strings or numbers with different digit lengths, failing to treat missing digits as 0 (for LSD) or as terminators (for MSD) leads to incorrect lexicographic order. In LSD, shorter numbers are implicitly padded with leading zeros; in MSD, shorter strings should sort before longer strings that share the same prefix.

5. Choosing Wrong Radix for Data Size: Using base 10 for 32-bit integers (10 passes) when base 256 (4 passes) is available wastes time. Conversely, using radix 65536 for n = 1000 wastes memory and cache for the count array. Profile and choose radix based on n and key width.

Best Practices for Production Code

Validate Inputs Early: Check for empty arrays, None values, and mixed types. Radix sort assumes homogeneous integer or string data; passing floats without conversion or mixed types will fail. Add assertions or type checks at the function entry.

Reuse Buffers: Instead of allocating a new output array on every pass, allocate two buffers and ping-pong between them. This halves allocation overhead and improves cache locality. Many high-performance implementations allocate output once and swap references.

Consider Hybrid Approaches: For small arrays (n < 64), insertion sort may be faster than radix sort due to lower constant factors. Implement a threshold check: if n is small, delegate to Python's built-in Timsort or insertion sort. This is similar to how optimized quicksort handles small partitions.

Test Stability Explicitly: Create test cases with duplicate keys and verify that original order is preserved. For example, sort [(5, 'a'), (3, 'b'), (5, 'c')] by the numeric key and ensure (5, 'a') remains before (5, 'c'). Stability bugs are silent and hard to detect without explicit tests.

Document Radix and Assumptions: Clearly document whether your implementation handles negatives, what radix it uses, and what key types it supports. Future maintainers need to know that changing from base 256 to base 10 will affect performance and that the function is not suitable for arbitrary objects.

10. Interview Questions

Radix sort is a favorite in technical interviews because it tests understanding of non-comparative sorting, stability, complexity analysis, and practical trade-offs. Here are common questions and how to approach them.

Q1: Why does radix sort require a stable subroutine? What happens if it is unstable?

Answer: Radix sort builds the final order incrementally, one digit at a time. Stability ensures that the ordering established by less significant digits is preserved when sorting by more significant digits. If the subroutine is unstable, two numbers with the same current digit could be reordered arbitrarily, destroying the work of previous passes. For example, sorting [21, 12] by LSD: after units pass, order is [21, 12] (1 before 2). Sorting by tens with an unstable sort could produce [12, 21] or [21, 12] nondeterministically, but only [12, 21] is correct. Without stability, the algorithm is incorrect. In an interview, walk through a small example like [170, 090, 802] to demonstrate.

Q2: What is the time complexity of radix sort? Is it really O(n)? When would you prefer quicksort over radix sort?

Answer: Time is O(d * (n + k)), where d is number of digits, n is number of elements, k is radix. It is O(n) only when d and k are constants, e.g., sorting 32-bit integers with radix 256 gives d=4, k=256, so O(4*(n+256)) = O(n). It is not truly O(n) for arbitrary integers where d grows with n, such as sorting n numbers up to n^2, where d = O(log_k n). Prefer quicksort when keys are variable-length, not digit-decomposable (e.g., custom objects with comparator), when n is small (quicksort has lower constants), or when memory is extremely constrained and O(n) auxiliary space is unacceptable. Also prefer quicksort when you need in-place sorting without extra allocations.

Q3: How would you extend radix sort to handle negative integers and floating-point numbers?

Answer: For negatives: partition into negatives and non-negatives, sort each by absolute value using LSD, then reverse the sorted negatives and concatenate: sorted_negatives_reversed + sorted_positives. Alternatively, bias signed 32-bit ints by adding 2^31 to map [-2^31, 2^31-1] to [0, 2^32-1], sort as unsigned, then subtract bias. For floats: reinterpret IEEE 754 bits as integers. For positive floats, the bit pattern as an integer sorts correctly. For negative floats, flip all bits (or flip sign bit) because their integer ordering is reversed. Handle special values like -0.0, NaN, and infinities separately. Mention that Python's struct module can be used to reinterpret bits, or use numpy's view.

Q4: Explain the difference between LSD and MSD radix sort. Which would you use to sort variable-length strings?

Answer: LSD processes from least significant digit to most, iteratively, always doing d passes, and is simpler and iterative. MSD processes from most significant digit, recursively bucketing, and can terminate early for buckets of size 1. For variable-length strings, MSD is preferred because it naturally handles different lengths by treating missing characters as smaller than any character, and it can avoid processing trailing characters of strings that are already distinguished by early characters. LSD would require padding all strings to the maximum length, wasting work. Describe how MSD buckets by first character, then recursively sorts each bucket by second character, etc., similar to trie traversal.

Q5: How would you implement radix sort for a large dataset that does not fit in memory (external sorting)?

Answer: For external radix sort, you can perform a most-significant-digit first distribution pass that partitions the data on disk into buckets by the top digit(s) without loading everything into RAM. Each bucket corresponds to a range of values and can be written to a separate file. Then recursively sort each bucket file individually (either in memory if it fits, or with further passes). This is similar to bucket sort for external data. Because radix sort's passes are sequential and each pass only needs to scan the data once, it is more I/O efficient than comparison-based external mergesort which requires multiple merge phases. Mention that you would use double buffering and asynchronous I/O to overlap computation and disk access, and that SSDs benefit from larger radix to reduce passes and thus I/O rounds.