51: LSD Radix Sort Program in Python | Step-by-Step Implementation Using Buckets

Understanding LSD Radix Sort

LSD Radix Sort stands for Least Significant Digit Radix Sort and represents a non-comparison-based sorting algorithm that processes integer keys one digit at a time. Unlike comparison sorts such as quicksort or merge sort, radix sort exploits the positional representation of numbers to achieve linear time complexity under certain conditions. The algorithm begins by examining the least significant digit, which is the ones position, and progresses toward the most significant digit. This approach allows the algorithm to sort numbers without ever directly comparing two elements against each other. The strength of LSD Radix Sort lies in its stability during each pass, meaning that numbers with the same digit at the current position retain their relative order from the previous pass. That property is essential for the algorithm to produce a fully sorted list once all digit positions have been processed.

The YouTube tutorial by Amulya's Academy walks through a complete Python implementation of LSD Radix Sort using the bucket method. The bucket method works by creating ten separate containers, one for each decimal digit from 0 through 9, and distributing numbers into those containers based on the digit currently being examined. After all numbers have been distributed, they are collected back in bucket order, which places numbers with smaller digits first. The process repeats for the tens digit, then the hundreds digit, and so on until the maximum number of digits in the input list has been processed. The result is a list sorted in ascending order without any explicit comparison between individual elements.

How Digit Extraction Works

A core technical component of LSD Radix Sort is the extraction of individual digits from each number. The tutorial explains how Python's integer division operator and modulo operator work together to isolate the digit at any given position. To extract the ones digit, the code takes a number modulo ten. To extract the tens digit, the code first divides the number by ten using integer division and then applies modulo ten to the result. This pattern generalizes to higher positions by dividing by increasing powers of ten before applying the modulo operation. The tutorial introduces an exp variable that starts at one and is multiplied by ten after each complete pass, allowing the same digit extraction formula to be reused for every position.

The explanation of digit extraction is particularly valuable for learners who may be familiar with basic Python syntax but have not yet encountered the mathematical operations required for digit isolation. Understanding how to break a number into its positional components is a foundational skill that appears in many algorithm problems beyond radix sort, including number conversion, digit counting, and bit manipulation tasks. The tutorial carefully demonstrates that the expression (num // exp) % 10 returns the correct digit for any non-negative integer when exp is a power of ten.

Creating and Managing Buckets

The bucket method requires allocating ten separate lists to hold numbers during each pass. The tutorial shows how to create these ten buckets using Python list comprehension, producing a list of ten empty lists in a single, readable line of code. List comprehension is a Python feature that allows concise construction of lists, and using it here eliminates the need for ten separate append statements or a verbose initialization loop. Each bucket is a nested list, meaning that the outer structure is a list containing ten inner lists. The first inner list corresponds to digit zero, the second to digit one, and so forth up to digit nine.

Once the buckets are initialized, the algorithm iterates over the current input list and appends each number to the bucket that matches its current digit. The tutorial emphasizes that append works at the end of a list, which automatically preserves stability during distribution. Because numbers are processed in their current order, any two numbers with the same digit are placed into the same bucket in the same relative order they appeared before. This stability is not incidental; it is a requirement for LSD Radix Sort to work correctly when moving to higher digit positions.

Collecting Numbers from Buckets

After all numbers have been distributed, the algorithm must collect them back into the original list. The collection phase iterates over the ten buckets in ascending order, from bucket zero to bucket nine, and within each bucket, iterates over the numbers in their stable order. The tutorial demonstrates the use of nested for loops to perform this collection, with the outer loop iterating over the bucket indices and the inner loop iterating over the elements within each bucket. Each number is copied back into the original list, overwriting the previous order of elements. By the end of the collection phase, the list is sorted according to the current digit position while maintaining stability for equal digits.

The tutorial also highlights a notable variation: by collecting buckets in reverse order, from bucket nine down to bucket zero, the algorithm can produce a descending sort instead of an ascending one. This flexibility comes at no additional computational cost and demonstrates a deeper understanding of how the bucket distribution process controls the final ordering. The ability to switch between ascending and descending order by changing only the collection loop is an elegant property of the radix sort structure.

Controlling the Main Sorting Loop

The outermost structure of the LSD Radix Sort implementation is a while loop that controls how many digit positions must be processed. The tutorial explains that the number of passes should equal the number of digits in the largest number within the input list. To determine this value, the code uses Python's built-in max function to find the largest element, then calculates how many times the exp variable must be multiplied by ten before it exceeds that maximum. The while loop condition checks whether the current exp value is still within the range of digits to process. When exp becomes larger than the maximum number, all digit positions have been handled, and the loop terminates.

This control mechanism ensures that the algorithm performs exactly the right number of passes. For example, if the largest number in the list is ninety-nine, the loop runs twice: once for the ones digit and once for the tens digit. If the largest number is one thousand five hundred, the loop runs four times. The tutorial emphasizes that using the maximum value to determine the number of passes prevents unnecessary extra work while guaranteeing that every relevant digit is processed.

Modifying the Original List In-Place

A design choice highlighted in the tutorial is that the radix sort function modifies the original list directly rather than returning a new sorted list. The in-place modification approach has practical implications for memory usage and API design. The function accepts a list as an argument and updates its contents through the distribution and collection cycles. By the time the function finishes, the original list variable contains the sorted order, and no new list object is returned. The tutorial notes that this implementation uses additional memory for the buckets, so the space complexity is not constant, but no separate output list is required beyond the temporary bucket structure.

Understanding in-place versus out-of-place sorting is an important concept for Python learners, as many built-in Python methods either mutate objects or return new ones based on design conventions. The tutorial's emphasis on updating the original list connects to broader discussions of mutability, side effects, and function return values in Python programming.

Practical Applications and Learning Goals

The LSD Radix Sort implementation covered in this tutorial is designed for non-negative integers, a typical constraint for introductory radix sort examples. Negative numbers require additional handling because the digit extraction logic assumes positive positional values, and floating-point numbers would require a different representation strategy entirely. The tutorial's deliberate scope keeps the implementation approachable while still conveying the essential algorithmic thinking behind radix sort.

For students of Data Structures and Algorithms, radix sort offers a valuable perspective on sorting that departs from the pairwise comparison paradigm. The linear time complexity in terms of the number of elements, multiplied by the number of digit positions, makes radix sort attractive for large datasets of integers with bounded digit counts. By the end of the tutorial, learners understand not only the Python implementation details such as list comprehension, nested loops, modulo, and integer division, but also the conceptual foundations that make LSD Radix Sort a stable and efficient algorithm for the right problem scenarios.