5 Best Ways to Implement Insertion Sort in Python

💡 Problem Formulation: How do you sort a list of numbers in ascending order using insertion sort in Python? Insertion sort is a simple and intuitive sorting algorithm that builds the final sorted array one item at a time. Given an input list, for example [8, 4, 3, 7], the desired output after sorting would be [3, 4, 7, 8].

Method 1: Traditional Insertion Sort

This method implements the classic insertion sort algorithm using a for-loop to iterate over the elements in the list and nested while-loop to place the current element into the correct position. It’s efficient for smaller lists but its performance decreases with larger lists due to its O(n^2) time complexity.

Here’s an example:

def insertion_sort(lst):
    for i in range(1, len(lst)):
        key = lst[i]
        j = i-1
        while j >= 0 and key < lst[j]:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = key
    return lst

print(insertion_sort([8, 4, 3, 7]))

Output of this code:

This code snippet performs the insertion sort by picking each element from the list and placing it in the precise location it needs to be. This process is repeated to sort the entire list.

Method 2: Insertion Sort with For-Loops

In this variant, two for-loops are used instead of a for-loop and a while-loop. This version is more Pythonic and clearer to some developers but retains the original algorithm’s time complexity.

Here’s an example:

def insertion_sort_for(lst):
    for i in range(1, len(lst)):
        key = lst[i]
        for j in range(i-1, -1, -1):
            if key < lst[j]:
                lst[j + 1] = lst[j]
                lst[j] = key
            else:
                break
    return lst

print(insertion_sort_for([8, 4, 3, 7]))

Output of this code:

By utilizing nested for-loops, the code iterates backward to find the right place for the selected element. The break statement is used to stop the iteration once the correct position is found.

Method 3: Insertion Sort with List Comprehensions

This approach simplifies the insertion sort algorithm by making use of Python’s powerful list comprehensions to reduce the amount of explicit looping and conditional checking.

Here’s an example:

def insertion_sort_comp(lst):
    for i in range(1, len(lst)):
        lst[:i+1] = [lst[i]] + [x for x in lst[:i] if x  lst[i]]
    return lst

print(insertion_sort_comp([8, 4, 3, 7]))

Output of this code:

This code snippet cleverly reconstructs the list around the current element, to be inserted using list comprehensions. Though more succinct, the readability might suffer for those unfamiliar with list comprehensions.

Method 4: Recursion-Based Insertion Sort

Instead of iterative loops, a recursive function can be used to perform the insertion sort. This method is more theoretical and favored in academic contexts to demonstrate the algorithm’s concept.

Here’s an example:

def insertion_sort_recursive(lst, n):
    if n = 0 and lst[j] > last):
        lst[j + 1] = lst[j]
        j = j -1
    lst[j + 1] = last

arr = [8, 4, 3, 7]
insertion_sort_recursive(arr, len(arr))
print(arr)

Output of this code:

The recursive function herein sorts all elements up to index n-1, then places the n‘th element in its proper position. This simulates the insertion sort without explicit looping constructs.

Bonus One-Liner Method 5: Using Python Built-ins

While not implementing insertion sort per se, Python’s built-in sorted function can sort any iterable quickly and efficiently with a more sophisticated algorithm under the hood.

Here’s an example:

print(sorted([8, 4, 3, 7]))

Output of this code:

This one-liner demonstrates Python’s simplicity and power by abstracting away the sorting algorithm. It is the recommended way to sort a list unless there is a specific need to use insertion sort.

Summary/Discussion

• Method 1: Traditional Insertion Sort. Time-proven and conceptually straightforward. Slow for larger datasets.
• Method 2: For-Loop Variant. More Pythonic syntax with clearer iteration. Same time complexity as the traditional approach.
• Method 3: List Comprehensions. Cleaner and more concise code. Can be less readable to those not well-versed in list comprehensions.
• Method 4: Recursion-Based. Demonstrates the algorithm in another paradigm. Not as efficient due to Python’s recursion depth limitations and overhead.
• Method 5: Python Built-ins. The most efficient and straightforward method for most sorting tasks. Does not actually implement insertion sort; uses Timsort instead.