Python Sorting Algorithms You Need To Know

There are a ton of sorting algorithms in computer science. In this article we’ll go over the basic sorting algorithms in Python. When I say basic, I don’t mean “easy”, I mean widely known. If you’re taking any computer science major, you’ll cover these sorting algorithms. The five sorting algorithms we’ll cover are bubble sort, heap sort, insertion sort, merge sort, and quicksort.

Python Sorting Algorithms – Bubble Sort

Bubble sort is probably going to be the slowest sorting algorithm I cover in Python. The only sorting algorithms with slower times are bogosort, the one where you randomly arrange the numbers and check if they’re sorted, and shellsort, the generalized version of insertion sort. A bubble sort of 50 numbers looks like the animation below.

What we’re doing in our bubble sort algorithm is going to every index in the array and comparing it to the indices that come before it, and if the number in the current index is greater than the number in the next index, we swap them. As we go through the array we’ll see the largest numbers “bubble” up to the end of the list, hence the name bubble sort.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(0, n-i-1):
            print(f"Comparing indicies {j} and {j+1}")
            print(f"The value in index {j} is {arr[j]}")
            print(f"The value in index {j+1} is {arr[j+1]}")
            if arr[j] > arr[j+1]:
                print(f"The value in index {j} is higher so we'll swap the values")
                arr[j], arr[j+1] = arr[j+1], arr[j]
                print(f"The array is now {arr} \n")

array = list(map(int, input("Input a list of numbers (separated by spaces)").split()))
print(f"Starting array is {array} \n")
bubble_sort(array)
print(f"Sorted array is {array}")

In terms of “Big O” time complexity, bubble sort has an average of O(n^2) which means that on average, the time it takes to do a bubble sort scales with the square of the size of the list. For example, it would take four times as long to sort a list that is of size 10000 than a list of size 5000 because it would be based on the square of the number of elements in the list. The best case time complexity of bubble sort is on the scale of O(n), and the worst case is still O(n^2).

Python Sorting Algorithms: Heap Sort in Python

Next up, in alphabetical order, is Heap Sort. Heap Sort is the process of sorting the list of numbers as if it were a heap structure. I think heap sort is the prettiest sort method, just look at it go! Heap sort is a core sorting algorithm that is taught in computer science. Usually in a data structures and algorithms course. Heap sort essentially treats the list as a binary tree and sorts the root nodes. You can find the Python Heap Sort Algorithm code on my GitHub.

What we’ll do for the Python implementation of the Heap Sort Algorithm (sometimes combined as heapsort) is define two functions, one heaping function, and one sorting function. The heap function basically sets up each index (i) as a root of a tree and then swaps it around with its left or right child to make sure that this specific heap or tree is in sorted order. The sort function executes the heap function for the first half of the array and then goes through the array backwards and swaps the first index with the current “root” index and performs a heap on them to ensure order.

def heap(arr, n, i):
    print(f"Heaping on index {i}")
    root = i 
    lc = 2*i + 1
    rc = 2*i + 2
    if lc < n  and arr[i] < arr[lc]:
        print(f"Swapping left child, {arr[lc]}, and root, {arr[i]}")
        root = lc
    if rc < n and arr[root] < arr[rc]:
        print(f"Swapping right child, {arr[rc]}, and root, {arr[root]}")
        root = rc
    if root != i:
        arr[i], arr[root] = arr[root], arr[i]
        print(f"Array is now {arr} \n")
        heap(arr, n, root)

def heap_sort(arr):
    n = len(arr)
    for i in range(n//2, -1, -1):
        heap(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heap(arr, i, 0)

array = list(map(int, input("Input a list of numbers (separated by spaces)").split()))
print(f"Starting array is {array} \n")
heap_sort(array)
print(f"Sorted array is {array}")

Heap sort has the same best, average, and worst case scenario time complexities of O(n log(n)). What? What is n log(n)? The tree structure sorting method of heapsort is what introduces this log(n) factor to our heap sort. When we use a heaping method, we have to go through the list via powers of 2, and when we take the opposite of the exponential (2^n) we get a logarithm. The n factor is because we have to go through each element.

Insertion Sort Python Sorting Algorithms Implementation

Insertion sort is a sorting algorithm that builds the final, sorted, list one element at a time, hence the name insertion sort. We’ll be building a Python implementation of insertion sort that will tell us what is happening as we sort through the code. The source code for this Python algorithm can be found in this insertion sort file.

Insertion sort is not as efficient as algorithms like quicksort, heapsort, or merge sort on large datasets, but on smaller ones, it is much faster. While it may not be as fast at higher sort volumes, the insertion sort sorting algorithm does have some nice advantages. It is stable, it can sort in place, and it can be adapted to sort as it receives a list in real time. It is also easy to implement. It’s not only an easy to implement Python algorithm, but it can even be implemented easily in C.

The insertion sort algorithm works by iterating through each element and keeping the first n elements sorted. Insertion sort compares the value of each index against every index in the list before it in reverse order. If the value of the index we are currently processing is less than the value of the index it is being compared against, we increment the index of the index being compared against. Otherwise, we set the value of the index being compared against to the value of the index we are processing and move on to the next index.

def insertion_sort(_list):
    for i in range(len(_list)-1):
        print("The reference index is", i)
        j = i
        print("The current index is", j)
        _next = _list[i+1]
        print("The value of the next element is", _next)
        while _list[j] > _next and j >= 0:
            print(f"The value of the current index ({_list[j]}) is greater than {_next}")
            print("We will decrement our current index and swap the values in indices", j+1, "and", j)
            _list[j+1] = _list[j]
            j -= 1
            print("The current index is now", j)
        _list[j+1] = _next
        print(f"The value in the current index ({_list[j]}) is less than the value of next element, next iteration \n")
        print(f"The current state of the array is {_list}")
    return _list

array = list(map(int, input("Input a list of numbers (separated by spaces)").split()))
print("Starting array is", array)
insertion_sort(array)
print("Sorted array is", array)

A visualization:

As you can see, insertion sort is a pretty slow sort, it’s actually a little slower than bubble sort in this example, but on average they’re about the same. Both O(n^2). Their best and worst case times are also the same, O(n) and O(n^2) respectively. I think of insertion sort almost like a backwards bubble sort in my head, instead of bubbling numbers up, it’s almost as if we’re bubbling them smaller ones down as we go instead.

Merge Sort Python Implementation

Here we’ll go over the Python Merge Sort Algorithm. This is one of the core sorting algorithms. The idea of the merge sort algorithm is to break down the list down until we get single elements and then do the sort by “merging” the elements together from lists of size 1, 2, 4, 8, etc until we get our whole list sorted back. Here is the source code for a Python Merge Sort Algorithm.

The Merge Sort Algorithm:

• Split the list into two
• Merge sort the left list
• Merge sort the right list

What is Merging?

• Starting with the index range that we are merging
• Compare elements in the left index to the right index
• Add the smaller one to the new sorted list
• Append the rest of the left or right arrays
• Replace the indices in the index range with the new sorted list

So how do we do a Python Merge Sort Algorithm?

def merge_sort(arr):
    n = len(arr)
    if n > 1:
        middle = n//2
        left = arr[:middle]
        right = arr[middle:]
        print(f"Array split into {left} and {right}")
        merge_sort(left)
        merge_sort(right)

        left_index = 0
        right_index = 0
        arr_index = 0
        left_size = len(left)
        right_size = len(right)

        print(f"Starting new merge for {arr}")
        # while both the left and right index counters are within the sizes of their respective arrays
        while left_index < left_size and right_index < right_size:
            # 
            if left[left_index] < right[right_index]:
                arr[arr_index] = left[left_index]
                left_index+=1
            else:
                arr[arr_index] = right[right_index]
                right_index+=1
            arr_index+=1
        
        while left_index < left_size:
            arr[arr_index] = left[left_index]
            left_index+=1
            arr_index+=1
        
        while right_index < right_size:
            arr[arr_index] = right[right_index]
            right_index+=1
            arr_index+=1
        
        print(f"Merge done - current array {arr}")

array = list(map(int, input("Input a list of numbers (separated by spaces)").split()))
print(f"Starting array is {array} \n")
merge_sort(array)
print(f"Sorted array is {array}")

This Python implementation of merge sort will show you which elements are being sorted, and what their sorted outcome is along the way. Below, I’ve included an animation of merge sort:

I think merge sort is also quite a pretty sort, but I still like heapsort better. In terms of time complexity, merge sort is also an O(n log(n)) on all fronts sorting algorithm. We can see why from the animation. Similarly to heap sort, merge sort also uses the split by two functionality and when we reverse the exponential, we get a logarithm.

Python Sorting Algorithms – Quick Sort

Finally, we get to the letter Q. Quicksort is a recursive divide-and-conquer algorithm that sorts in place. We pass three arguments to our Python Quicksort implementation. The whole array, the start index of the subarray being sorted, and the end index of the subarray being sorted. I’ve included the source code to quicksort a custom input and to animate quicksort for a randomized list of the integers 0 to 100

The recursive algorithm consists of 6 essential steps:

1. Check to make sure the starting index is less than the ending index
2. Define a pivot – we’ll just use the value of the array at the starting index in our example
   • Note: the pivot is an array value, not an index value, we will be using it to compare against the values in our array
3. Define a swap index – we’ll use the starting index in our example
4. Compare the value of every element between the start and end index in the array and increment our swap index for each one of those elements that’s less than or equal to the pivot and swap the two values
5. Swap the value at the starting index with the value in the swap index
6. Run quicksort again on the array to the left (index values start to swap minus one) and the array to the right (index values from swap plus one to end)

For our Python quicksort algorithm, we first create a pivot function, which does the “pivoting” involved in the quicksort algorithm. We identify the value at the starting index as our pivot value, and then set the initial left and right indices. The next step in our quicksort algorithm is to compare the value in the “right” index to the pivot value. While the pivot value is smaller and the “left” index is still left of (or less than) the right index, we decrement our right index by 1. Then we do the opposite thing to the left index, we increment it by 1 while it is less than the right index and the pivot value is greater than its value. At the end of our incrementing and decrementing, we swap the values in the right and left indices, and then the values in the start and right indices.

Then, to run quicksort, we create a quicksort function which does a sanity check, sets a pivot, and then recursively calls for the left and right sides after pivoting.

def pivot(array, start, end):
    pivot = array[start]
    left = start + 1
    right = end
    print("Pivot number is", pivot)
    print("Starting left and right indices are", left, "and", right)
    while True:
        while left <= right and array[right] >= pivot:
            right = right-1
            print(array[right+1], "is greater than or equal to", pivot, "so we shift the right index left to", right)
        while left <= right and array[left] <= pivot:
            left = left+1
            print(array[left-1], "is less than or equal to", pivot, "so we shift the left index right to", left)
        if left <=right:
            print("The left index is still on the left of the right index, so we'll swap the values")
            array[left], array[right] = array[right], array[left]
        else:
            print("The left index is further right than the right index so we don't need to swap")
            break
    
    print("We'll swap the values in indices", start, "and", right)
    array[start], array[right] = array[right], array[start]
    print("The array is now", array)
    return right

def quicksort(array, start, end):
    if start>=end:
        return
    p = pivot(array, start, end)
    quicksort(array, start, p-1)
    quicksort(array, p+1, end)

array = list(map(int, input("Input a list of numbers (separated by spaces)").split()))
print("Starting array is", array)
quicksort(array, 0, len(array)-1)
print(array)

Below, I’ve included a visualization of quicksort on a randomized list of integers from 0 to 100.

To learn more feel free to reach out to me @yujian_tang on Twitter, follow the blog, or join our Discord.

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.