Sorting Algorithms in Python: Selection Sort, Insertion Sort, Quicksort, Counting Sort, and Radix Sort

Every day, computers sort enormous amounts of data: products ranked by price, student grades arranged from highest to lowest, names listed alphabetically, or sensor readings organised by time. Sorting is one of the most fundamental tasks in computing.

In this lesson, you will learn five important sorting algorithms in Python, each with its own strategy, strengths, and weaknesses. By the end, you will be able to explain how each one works, write the Python code yourself, recognise when to use each one, and understand why choosing the right algorithm matters in real projects.

Think of sorting algorithms like strategies for arranging a deck of shuffled playing cards. Some strategies are slow but easy to understand. Others are blazingly fast. Some only work for certain kinds of cards. Let's explore them all.

Before we begin, let us quickly review a few ideas you will need to understand throughout this lesson.

What is a List (Array) in Python?

A list in Python is an ordered collection of items stored in a single variable. Think of it like a row of labelled boxes · each box holds one value, and each box has a position number called an index (starting from 0).

my_list = [7, 12, 9, 11, 3]
#           ^   ^   ^   ^  ^
# index:    0   1   2   3  4

• my_list[0] gives you 7 (the first item)
• my_list[4] gives you 3 (the last item)
• len(my_list) gives you 5 (the total number of items)

What is a Loop?

A loop repeats a block of code many times. In sorting, we use loops to scan through the list over and over again.

# A for loop visits each position
for i in range(5):      # i goes: 0, 1, 2, 3, 4
    print(i)

Output:

0
1
2
3
4

What is Swapping?

Swapping means exchanging the positions of two values. Python makes this beautifully easy:

a = 10
b = 99
a, b = b, a     # Swap! Now a=99 and b=10
print(a, b)

Output:

99 10

What is a Function?

A function is a named block of code you can reuse. You define it once and call it whenever you need it.

def greet(name):
    print("Hello,", name)

greet("Alice")   # calls the function
greet("Bob")

Output:

Hello, Alice
Hello, Bob

What is Recursion?

Recursion is when a function calls itself. It is used in Quicksort. Think of it like a mirror reflecting another mirror · each reflection is a smaller version of the same image.

def countdown(n):
    if n == 0:
        print("Done!")
        return
    print(n)
    countdown(n - 1)    # function calls itself with a smaller value

countdown(3)

Output:

3
2
1
Done!

Now you are ready. Let's start sorting!

What is Selection Sort?

Selection Sort is one of the simplest sorting strategies. The idea is this: scan the entire unsorted portion of the list, find the smallest value, and move it to the correct position at the front. Then repeat for the rest of the list.

The name comes from what it does: it selects the minimum value in each pass.

Real-World Analogy: Imagine you have a pile of 10 coins of different sizes scattered on a table. You scan all of them, pick out the smallest coin, and place it first in a row. Then you scan the remaining coins, pick the next smallest, and place it second. You keep doing this until all coins are in order from smallest to largest.

How Selection Sort Works (Step-by-Step)

Let's trace through a short array to make this concrete.

Starting array: [7, 12, 9, 11, 3]

Pass 1: Scan all 5 values. The smallest is 3 (at index 4). Swap 3 with the first element 7.

Before: [7, 12, 9, 11, 3]
After:  [3, 12, 9, 11, 7]

Pass 2: The first position is now sorted. Scan the rest: 12, 9, 11, 7. Smallest is 7 (at index 4). Swap 7 with 12.

Before: [3, 12, 9, 11, 7]
After:  [3,  7, 9, 11, 12]

Pass 3: Scan 9, 11, 12. Smallest is 9 · already in its correct spot. No swap needed.

[3, 7, 9, 11, 12]

Pass 4: Scan 11, 12. Smallest is 11 · already correct.

[3, 7, 9, 11, 12]  ✅ Sorted!

Simple Example: Selection Sort Without Swapping (Basic Version)

This is the simpler but slower approach · it removes the minimum and inserts it at the front:

mylist = [64, 34, 25, 5, 22, 11, 90, 12]

n = len(mylist)           # n = 8 (number of elements)

for i in range(n - 1):   # outer loop runs n-1 times
    min_index = i         # assume the current position holds the minimum

    for j in range(i + 1, n):    # inner loop scans the rest
        if mylist[j] < mylist[min_index]:
            min_index = j         # update if we find something smaller

    min_value = mylist.pop(min_index)   # remove the minimum
    mylist.insert(i, min_value)         # put it at position i

print(mylist)

Expected Output:

[5, 11, 12, 22, 25, 34, 64, 90]

Let's explain every line:

What happens if the input is already sorted? Try changing the list to [1, 2, 3, 4, 5] and running the code. How many swaps happen?

The Shifting Problem

There is a hidden cost in the basic version above. When you use .pop() to remove an element, Python must slide every element after it one step down to fill the gap. When you use .insert(), Python must slide every element after it one step up to make room.

For a list with 1,000 elements, this hidden sliding happens thousands of times · and it all costs time.

Visual: Removing element at index 2 from [A, B, C, D, E]:

[A, B, _, D, E]   → gap created
[A, B, D, E]      → D and E slide left to fill it

This is slow. We can fix it.

Improved Selection Sort: Using Swapping

Instead of removing and inserting, simply swap the minimum value with the element at position i. This avoids all that sliding.

mylist = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(mylist)

for i in range(n):
    min_index = i             # assume position i is the minimum

    for j in range(i + 1, n):
        if mylist[j] < mylist[min_index]:
            min_index = j     # found a smaller value

    # Swap the found minimum with the element at position i
    mylist[i], mylist[min_index] = mylist[min_index], mylist[i]

print(mylist)

Expected Output:

[5, 11, 12, 22, 25, 34, 64, 90]

The result is exactly the same, but internally no elements shift around. Only two elements are swapped. This is much more efficient.

Why does swapping work here? Because we don't care where the "large" element we displaced goes · we haven't sorted it yet anyway. We only need the minimum in the correct spot.

Selection Sort Time Complexity

Time complexity is a way to measure how much work an algorithm does as the input grows.

For an array of n values:

• The outer loop runs approximately n times
• The inner loop scans on average n/2 elements
• Total work: n × n/2 = n²/2

We write this as O(n²) (pronounced "Big-O of n squared").

What does this mean in practice?

The work grows very fast as the list gets bigger. Selection Sort is practical only for small lists (a few hundred items at most).

What is Insertion Sort?

Insertion Sort keeps a growing sorted region at the left of the list. It takes one value at a time from the unsorted region on the right and inserts it into the correct position in the sorted region.

The name says it all: you insert each element where it belongs.

Real-World Analogy: Think of sorting a hand of playing cards. You pick up one card at a time from the table. For each new card you pick up, you look at your sorted hand from right to left, and slip the new card into the correct gap. This is exactly Insertion Sort.

How Insertion Sort Works (Step-by-Step)

Starting array: [7, 12, 9, 11, 3]

Step 1: The first element 7 is already a "sorted section" of one.

Sorted: [7] | Unsorted: [12, 9, 11, 3]

Step 2: Take 12. Is 12 > 7? Yes. So 12 stays in place.

Sorted: [7, 12] | Unsorted: [9, 11, 3]

Step 3: Take 9. Is 9 > 12? No. Move 12 right. Is 9 > 7? Yes. Insert 9 before 12.

Sorted: [7, 9, 12] | Unsorted: [11, 3]

Step 4: Take 11. Is 11 > 12? No. Move 12 right. Is 11 > 9? Yes. Insert 11 before 12.

Sorted: [7, 9, 11, 12] | Unsorted: [3]

Step 5: Take 3. It's smaller than everything. Move 12, 11, 9, 7 all right. Insert 3 at the start.

Sorted: [3, 7, 9, 11, 12] ✅

Simple Example: Basic Insertion Sort

mylist = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(mylist)

for i in range(1, n):          # start from index 1 (first is already "sorted")
    insert_index = i
    current_value = mylist.pop(i)    # remove the current element to insert

    for j in range(i - 1, -1, -1):  # scan the sorted part from right to left
        if mylist[j] > current_value:
            insert_index = j         # the current_value should go here or earlier

    mylist.insert(insert_index, current_value)   # put it in the right place

print(mylist)

Expected Output:

[5, 11, 12, 22, 25, 34, 64, 90]

Let's break down every piece:

Thinking Prompt: What if the current_value is bigger than everything in the sorted part? Walk through what happens to insert_index.

The Hidden Shifting Problem (Again)

Just like Selection Sort, using .pop() and .insert() causes hidden shifting of elements in memory. If the array has 1,000 elements and we need to insert a small value at the beginning, all 999 other elements must slide one step to the right.

Improved Insertion Sort: In-Place Shifting

Instead of removing and inserting, we copy the value we want to insert and then shift elements one by one to make space · stopping as soon as we find where the value belongs.

mylist = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(mylist)

for i in range(1, n):
    insert_index = i
    current_value = mylist[i]       # copy the value (don't remove it yet)

    for j in range(i - 1, -1, -1):
        if mylist[j] > current_value:
            mylist[j + 1] = mylist[j]   # shift this element one step to the right
            insert_index = j
        else:
            break                        # stop early — we found where it belongs

    mylist[insert_index] = current_value    # place the value in its correct spot

print(mylist)

Expected Output:

[5, 11, 12, 22, 25, 34, 64, 90]

The key improvements:

• mylist[j + 1] = mylist[j] · instead of shifting the whole array, we only shift elements one at a time, and stop (break) as soon as we no longer need to shift
• mylist[insert_index] = current_value · once we know exactly where the value belongs, place it there

Why does break help? If we are inserting 50 into [10, 20, 30, 40, 60, 70, 80], we only need to shift 60, 70, and 80. As soon as we see 40 < 50, we stop. Without break, we would check 40, 30, 20, 10 unnecessarily.

Insertion Sort Time Complexity

Like Selection Sort, Insertion Sort also has O(n²) average-case time complexity. On average, each of the n elements is compared against n/2 other elements.

However, Insertion Sort has an important advantage:

• Best Case (already sorted): O(n) · it only needs to confirm each element is in place, so the inner loop almost never runs.
• Worst Case (reverse sorted): O(n²) · every element must travel all the way to the front.

This makes Insertion Sort much better than Bubble Sort or Selection Sort on nearly-sorted data · a common real-world scenario.

What is Quicksort?

Quicksort is one of the fastest sorting algorithms in practice. As the name suggests, it is genuinely quick.

The core idea:

1. Choose one element from the array called the pivot
2. Rearrange all other elements so that values smaller than the pivot are on its left, and values larger than the pivot are on its right
3. Now the pivot is in its final correct position
4. Repeat the same process recursively on the left sub-array and the right sub-array

The algorithm keeps dividing the problem in half until the sub-arrays are too small to sort (size 0 or 1), at which point they are already sorted.

Real-World Analogy: Imagine sorting a pile of exam papers by grade. You pick one paper as your "pivot grade." You put all papers below that grade on the left pile, and all papers above it on the right pile. Then you do the same thing for each pile, and each sub-pile, until all piles are too small to need sorting. The final arrangement is in order.

Understanding Recursion in Quicksort

Before seeing the code, let us make sure recursion makes sense.

A recursive function solves a big problem by solving smaller versions of the same problem. It needs two things:

1. A base case: the simplest possible input where we just return (e.g., a list of 0 or 1 elements is already sorted)
2. A recursive case: split the problem and call itself on the smaller pieces

# Example: recursively count down
def countdown(n):
    if n <= 0:          # base case: stop here
        print("Blastoff!")
        return
    print(n)
    countdown(n - 1)    # recursive case: call itself with a smaller value

countdown(4)

Output:

4
3
2
1
Blastoff!

Quicksort works the same way · it calls itself on smaller and smaller sub-arrays until they are all sorted.

How Quicksort Works (Step-by-Step)

Starting array: [11, 9, 12, 7, 3]

We choose the last element as the pivot: 3

Step 1: All other values (11, 9, 12, 7) are greater than 3. Since 3 is the smallest, everything must go to its right. Swap 3 with the first element 11:

[3, 9, 12, 7, 11]

3 is now in its final position!

Step 2: Now sort [9, 12, 7, 11] to the right of 3. Choose 11 as pivot.

• 7 is less than 11 → goes left
• 9 is less than 11 → goes left
• 12 is greater than 11 → goes right
• After rearranging: [9, 7, 11, 12]
• 11 is in its final position!

Step 3: Sort [9, 7]. Choose 7 as pivot. 9 > 7, so swap:

[7, 9]

Both are in final position!

Final sorted array: [3, 7, 9, 11, 12] ✅

Quicksort Code in Python

Quicksort needs two functions working together:

• partition() · rearranges values around a pivot
• quicksort() · recursively calls itself on sub-arrays

def partition(array, low, high):
    pivot = array[high]     # choose the last element as pivot
    i = low - 1             # i tracks the "boundary" of smaller elements

    for j in range(low, high):        # scan from low to high-1
        if array[j] <= pivot:         # if current element is <= pivot
            i += 1                    # expand the "smaller" region
            array[i], array[j] = array[j], array[i]   # swap it in

    # Place the pivot between the two regions
    array[i + 1], array[high] = array[high], array[i + 1]
    return i + 1                      # return pivot's final index


def quicksort(array, low=0, high=None):
    if high is None:
        high = len(array) - 1         # initialise high on first call

    if low < high:                    # base case: if 0 or 1 elements, stop
        pivot_index = partition(array, low, high)   # partition and get pivot position
        quicksort(array, low, pivot_index - 1)      # sort the LEFT sub-array
        quicksort(array, pivot_index + 1, high)     # sort the RIGHT sub-array


mylist = [64, 34, 25, 5, 22, 11, 90, 12]
quicksort(mylist)
print(mylist)

Expected Output:

[5, 11, 12, 22, 25, 34, 64, 90]

Line-by-Line Explanation of partition()

pivot = array[high]

We pick the last element as the pivot. (Other choices are possible · first element, random element, etc.)

i = low - 1

i is a pointer that tracks the rightmost position of the "smaller than pivot" region. It starts just before the region begins.

for j in range(low, high):
    if array[j] <= pivot:
        i += 1
        array[i], array[j] = array[j], array[i]

We scan every element from low to high-1. If an element is ≤ pivot, we expand the "smaller" region (move i right) and swap that element into it.

array[i + 1], array[high] = array[high], array[i + 1]
return i + 1

After scanning everything, we place the pivot itself at position i+1 · exactly between the "smaller" and "larger" regions. This is its final sorted position.

Line-by-Line Explanation of quicksort()

if low < high:

Base case: if low equals or exceeds high, there are 0 or 1 elements · already sorted.

pivot_index = partition(array, low, high)
quicksort(array, low, pivot_index - 1)
quicksort(array, pivot_index + 1, high)

After partitioning, the pivot is in place. We recursively sort everything to its left and everything to its right.

Thinking Prompt: After partition() runs, can the pivot ever move again? Why or why not?

Quicksort Time Complexity

The average case of O(n log n) is what makes Quicksort so popular in practice. It is dramatically faster than Selection Sort or Insertion Sort for large datasets.

Why is O(n log n) better than O(n²)?

Quicksort handles a million items with about 20 million operations. Selection Sort would need a trillion operations for the same task. The difference is enormous.

What is Counting Sort?

All the sorting algorithms we have studied so far work by comparing values to each other: "Is this bigger than that?" But Counting Sort takes a completely different approach · it counts how many times each value appears.

Instead of rearranging the original elements by comparing them, Counting Sort:

1. Creates a "count array" where position i stores how many times the value i appears in the input
2. Uses those counts to reconstruct a perfectly sorted array

Real-World Analogy: Imagine you have a bag of coloured balls · some red (value 1), some blue (value 2), some green (value 3). Instead of sorting them by comparing each ball to another, you simply count: "3 red, 5 blue, 2 green." Then you put them back in order: put all 3 red ones first, then 5 blue, then 2 green. Done · and you never needed to compare red to blue!

Conditions for Counting Sort

Counting Sort only works properly when:

1. Values must be non-negative integers · because we use each value as an index in the count array. A negative index would be outside the array.

1. Values must have a limited range · if your values can be anywhere from 0 to 1,000,000, the count array needs 1,000,001 positions, which wastes memory. Counting Sort works best when the range of values (k) is small compared to the number of values (n).

Good use case: Sorting 10,000 test scores all between 0 and 100. (k=101 is tiny compared to n=10,000)

Bad use case: Sorting 10 phone numbers. (k could be up to 9,999,999,999 · a huge count array for just 10 numbers)

How Counting Sort Works (Step-by-Step)

Starting array: [2, 3, 0, 2, 3, 2] Values range from 0 to 3, so our count array has 4 positions (indices 0, 1, 2, 3).

Step 1: Create an empty count array:

countArray = [0, 0, 0, 0]
#index:        0  1  2  3

Step 2: Go through each value in the original array and increment the count at that index.

• Value 2 → countArray[2] += 1 → [0, 0, 1, 0]
• Value 3 → countArray[3] += 1 → [0, 0, 1, 1]
• Value 0 → countArray[0] += 1 → [1, 0, 1, 1]
• Value 2 → countArray[2] += 1 → [1, 0, 2, 1]
• Value 3 → countArray[3] += 1 → [1, 0, 2, 2]
• Value 2 → countArray[2] += 1 → [1, 0, 3, 2]

Final count array: [1, 0, 3, 2]

This tells us: there is 1 zero, 0 ones, 3 twos, and 2 threes.

Step 3: Rebuild the sorted array from the count array:

• countArray[0] = 1 → add one 0 → [0]
• countArray[1] = 0 → add no 1s → [0]
• countArray[2] = 3 → add three 2s → [0, 2, 2, 2]
• countArray[3] = 2 → add two 3s → [0, 2, 2, 2, 3, 3]

Sorted array: [0, 2, 2, 2, 3, 3] ✅

Simple Example: Counting Sort in Python

def countingSort(arr):
    max_val = max(arr)              # find the highest value
    count = [0] * (max_val + 1)    # create count array of size max_val+1, all zeros

    while len(arr) > 0:
        num = arr.pop(0)            # take one value from the input array
        count[num] += 1             # increment its count

    for i in range(len(count)):    # go through every possible value
        while count[i] > 0:        # as many times as it appears
            arr.append(i)          # add that value to the sorted array
            count[i] -= 1          # decrement the count

    return arr


mylist = [4, 2, 2, 6, 3, 3, 1, 6, 5, 2, 3]
mysortedlist = countingSort(mylist)
print(mysortedlist)

Expected Output:

[1, 2, 2, 2, 3, 3, 3, 4, 5, 6, 6]

Line-by-Line Explanation

max_val = max(arr)

Find the largest value. We need this to know how big to make the count array.

count = [0] * (max_val + 1)

Create a count array filled with zeros. The +1 is because we need indices from 0 up to and including max_val. For example, if max_val is 6, we need indices 0, 1, 2, 3, 4, 5, 6 · that's 7 positions.

while len(arr) > 0:
    num = arr.pop(0)
    count[num] += 1

Remove each element from the input array and record its count. arr.pop(0) removes the first element and returns it.

for i in range(len(count)):
    while count[i] > 0:
        arr.append(i)
        count[i] -= 1

Rebuild the sorted array. For each index i, add the value i exactly count[i] times.

What happens if all values are the same? Try [3, 3, 3, 3]. What does the count array look like?

Counting Sort Time Complexity

The time complexity of Counting Sort depends on two things:

• n · the number of values to sort
• k · the range of possible values (highest value + 1)

Why O(n + k)? The algorithm has two phases:

• Phase 1 (counting): visits n elements → O(n)
• Phase 2 (rebuilding): visits k positions in the count array → O(k)
• Total: O(n + k)

When k is small compared to n, this is very fast. When k is much larger than n, it becomes slow and memory-wasteful.

What is Radix Sort?

Radix Sort is an advanced sorting algorithm that extends the idea of Counting Sort. It sorts integers by processing them one digit at a time, starting from the least significant digit (the units column) and working towards the most significant digit (the thousands column, etc.).

The word "radix" means "base." In the normal decimal number system (base 10), there are 10 possible digits: 0 through 9. Radix Sort uses 10 buckets (one for each digit) to group numbers by their current digit, then collects them back in order.

Real-World Analogy: Imagine sorting 100 library books by their 3-digit code. First, sort all books by the last digit of their code (units) into 10 piles (pile 0, pile 1, ..., pile 9). Collect the piles in order. Next, sort by the middle digit (tens) into 10 piles and collect again. Finally, sort by the first digit (hundreds). After three passes, all books are in perfect order · without ever comparing two books to each other!

Why Does Starting from the Rightmost Digit Work?

This seems counterintuitive at first. Why start from the least important digit?

The answer: because we sort in a stable way (elements with the same digit keep their relative order from previous rounds). By the time we sort on the most significant digit, all the finer distinctions (units, tens) are already correctly ordered within each group.

Think of it like sorting by last name, then first name. If you first sort alphabetically by first name in a stable way, and then sort by last name in a stable way, people with the same last name will be ordered by first name · exactly what you want.

What is Stable Sorting?

A sorting algorithm is stable if elements with equal values maintain their original relative order after sorting.

Example: Consider [3a, 1, 3b, 2] where 3a and 3b both have value 3, but 3a came first.

• Stable sort result: [1, 2, 3a, 3b] · 3a still comes before 3b
• Unstable sort result: [1, 2, 3b, 3a] · the order of equal elements is mixed up

Radix Sort requires stable sorting within each digit pass, or the result will be incorrect. When we process the tens digit, we must not disturb the work done on the units digit.

How Radix Sort Works (Step-by-Step)

Starting array: [33, 45, 40, 25, 17, 24]

Pass 1: Sort by units digit (rightmost)

Examine the units digit of each number:

• 33 → units digit is 3
• 45 → units digit is 5
• 40 → units digit is 0
• 25 → units digit is 5
• 17 → units digit is 7
• 24 → units digit is 4

Place each number in the corresponding bucket (0 through 9):

Bucket 0: [40]
Bucket 1: []
Bucket 2: []
Bucket 3: [33]
Bucket 4: [24]
Bucket 5: [45, 25]    ← both have units digit 5; 45 came first, so stays first (stable)
Bucket 6: []
Bucket 7: [17]
Bucket 8: []
Bucket 9: []

Collect from buckets in order (bucket 0 first, then 1, etc.):

[40, 33, 24, 45, 25, 17]

Pass 2: Sort by tens digit

Examine the tens digit:

• 40 → tens digit is 4
• 33 → tens digit is 3
• 24 → tens digit is 2
• 45 → tens digit is 4
• 25 → tens digit is 2
• 17 → tens digit is 1

Place in buckets:

Bucket 1: [17]
Bucket 2: [24, 25]   ← 24 came before 25 in the list, and stays that way (stable!)
Bucket 3: [33]
Bucket 4: [40, 45]

Collect from buckets:

[17, 24, 25, 33, 40, 45]  ✅ Sorted!

Notice that 24 correctly comes before 25, and 40 correctly comes before 45, because we preserved the order from Pass 1 (stable sorting).

Radix Sort Code in Python

mylist = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", mylist)

radixArray = [[], [], [], [], [], [], [], [], [], []]   # 10 buckets for digits 0-9
maxVal = max(mylist)    # find the largest value
exp = 1                 # start with the units digit (10^0 = 1)

while maxVal // exp > 0:    # keep going as long as there are digits to process

    while len(mylist) > 0:
        val = mylist.pop()               # take a value from the back of the list
        radixIndex = (val // exp) % 10  # find the current digit
        radixArray[radixIndex].append(val)   # put it in the right bucket

    for bucket in radixArray:
        while len(bucket) > 0:
            val = bucket.pop()       # take from the END of bucket (stable!)
            mylist.append(val)       # add to the beginning of rebuilt list

    exp *= 10    # move to the next digit (tens, hundreds, ...)

print(mylist)

Expected Output:

Original array: [170, 45, 75, 90, 802, 24, 2, 66]
[2, 24, 45, 66, 75, 90, 170, 802]

Line-by-Line Explanation

radixArray = [[], [], [], [], [], [], [], [], [], []]

Ten empty buckets · one for each possible digit (0 through 9).

maxVal = max(mylist)
exp = 1

We need to know how many digit positions to process. exp starts at 1 (units), then becomes 10 (tens), 100 (hundreds), etc.

while maxVal // exp > 0:

This loop runs once per digit. For maxVal = 802:

• When exp = 1: 802 // 1 = 802 > 0 ✅
• When exp = 10: 802 // 10 = 80 > 0 ✅
• When exp = 100: 802 // 100 = 8 > 0 ✅
• When exp = 1000: 802 // 1000 = 0, so loop stops ✅

val = mylist.pop()
radixIndex = (val // exp) % 10

This extracts the digit at the current position. Let's trace for val = 170 when exp = 10:

• 170 // 10 = 17
• 17 % 10 = 7
• So the tens digit of 170 is 7 → goes into bucket 7 ✅

for bucket in radixArray:
    while len(bucket) > 0:
        val = bucket.pop()
        mylist.append(val)

We collect values from all buckets in order (bucket 0 first, then 1, then 2, ...). Using .pop() takes from the END of each bucket, which maintains stability.

exp *= 10

Move to the next digit position.

Radix Sort with Bubble Sort as the Underlying Sorter

Radix Sort can actually use any stable sorting algorithm to sort within each bucket. Here is a version that uses Bubble Sort:

def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


def radixSortWithBubbleSort(arr):
    max_val = max(arr)
    exp = 1

    while max_val // exp > 0:
        radixList = [[], [], [], [], [], [], [], [], [], []]

        for num in arr:
            radixIndex = (num // exp) % 10
            radixList[radixIndex].append(num)

        for bucket in radixList:
            bubbleSort(bucket)    # sort within each bucket

        i = 0
        for bucket in radixList:
            for num in bucket:
                arr[i] = num
                i += 1

        exp *= 10


mylist = [170, 45, 75, 90, 802, 24, 2, 66]
radixSortWithBubbleSort(mylist)
print(mylist)

Expected Output:

[2, 24, 45, 66, 75, 90, 170, 802]

Radix Sort Time Complexity

The formal complexity is O(n · k) where:

• n = number of values to sort
• k = number of digits in the largest value

Example scenarios:

• 1,000,000 values, all ≤ 999 (3 digits): O(n · 3) ≈ O(n) · super fast!
• 1,000 values, largest is a 1,000-digit number: O(n · 1000) ≈ O(n²) · slow

Radix Sort is most effective when k is small relative to n.

Mistake 1: Off-By-One Error in Selection Sort

❌ Wrong:

for i in range(n):       # outer loop
    for j in range(i, n):   # inner loop starts at i, not i+1

When j starts at i, the algorithm compares an element with itself, which wastes a comparison and can cause issues.

✅ Correct:

for i in range(n):
    min_index = i
    for j in range(i + 1, n):   # start one position AFTER i

Mistake 2: Forgetting the break in Improved Insertion Sort

❌ Wrong:

for j in range(i - 1, -1, -1):
    if arr[j] > current_value:
        arr[j + 1] = arr[j]
        insert_index = j
    # No break! The loop continues even after finding the right spot

This means even after finding where current_value belongs, the algorithm keeps checking smaller indices unnecessarily. It still gives the right answer, but wastes time.

✅ Correct:

for j in range(i - 1, -1, -1):
    if arr[j] > current_value:
        arr[j + 1] = arr[j]
        insert_index = j
    else:
        break    # stop as soon as we've gone past where it belongs

Mistake 3: Using Counting Sort with Negative or Float Values

❌ Wrong:

arr = [-5, 3, 1, -2, 4]
max_val = max(arr)          # max_val = 4
count = [0] * (max_val + 1) # creates [0, 0, 0, 0, 0]

for num in arr:
    count[num] += 1     # ERROR! count[-5] is index -5, which is index 0 in Python
                        # This causes incorrect behaviour (not a crash, but wrong results)

✅ Correct: Only use Counting Sort on non-negative integers. If you have negative values, you need to shift them first or use a different algorithm.

Mistake 4: Modifying the Original List in Sorting Functions

❌ Wrong:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        ...    # This modifies arr directly

original = [3, 1, 2]
sorted_list = selection_sort(original)
print(original)    # [1, 2, 3] — the original was changed too!

✅ Correct: Make a copy first:

def selection_sort(arr):
    arr = arr[:]    # create a copy
    n = len(arr)
    ...

Mistake 5: Quicksort Stack Overflow on Very Large Sorted Input

Quicksort is recursive. If the input is already sorted and you always pick the last element as the pivot, the algorithm degrades to O(n²) and makes n recursive calls. For very large inputs, Python may run out of "call stack" space and crash.

✅ Solutions:

• Randomly shuffle the input before sorting
• Choose a random pivot instead of always the last element
• Use Python's built-in sorted() for large datasets, which uses Timsort · a hybrid algorithm that handles these cases gracefully

Mistake 6: Forgetting That Radix Sort Requires Stable Sorting

If you implement the inner sorting step of Radix Sort in an unstable way (e.g., picking elements from the wrong end of buckets), the final result may be incorrectly ordered even though each pass appears to work.

✅ Always test: After Radix Sort, verify that the output is identical to what sorted() would produce for the same input.