Implementation of Insertion Sort Algorithm in Python

Insertion sort is an algorithm used to sort a list of items in ascending, descending or any other custom order. In this article, we’ll implement a basic version of insertion sort algorithm in Python which can sort a given list of numbers in ascending order. We’ll then explore several practical variations, including sorting in descending order and handling custom objects with flexible sorting criteria.

Prerequisites:

Basic Insertion Sort Implementation

Let’s start with the standard iterative implementation of insertion sort. This version sorts an array in ascending order by repeatedly taking an element and inserting it into its correct position in the already sorted portion of the array.

def insertion_sort(arr):
  # Handle empty or single-element arrays
  if len(arr) <= 1:
    return arr
    
  # Iterate through array starting from second element
  for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    
    # Move elements greater than key ahead
    while j >= 0 and arr[j] > key:
      arr[j + 1] = arr[j]
      j -= 1
    
    # Place key in its correct position
    arr[j + 1] = key
    
  return arr

# Let's try it with a simple array
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = insertion_sort(arr)
print(f"Sorted array: {sorted_arr}")
# Output: Sorted array: [11, 12, 22, 25, 34, 64, 90]

# Works great with duplicates too!
arr_with_duplicates = [4, 3, 2, 4, 1, 2]
sorted_arr = insertion_sort(arr_with_duplicates)
print(f"Sorted array with duplicates: {sorted_arr}")
# Output: Sorted array with duplicates: [1, 2, 2, 3, 4, 4]

Sorting in Descending Order

Sometimes we need to sort items in reverse order. This implementation modifies the basic insertion sort to arrange elements from largest to smallest. The only difference is in the comparison operator - we use < instead of > to achieve descending order. This is particularly useful when you need to find top-performing items or display data in reverse order.

def insertion_sort_desc(arr):
  if len(arr) <= 1:
    return arr
    
  for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    
    # Notice the < operator instead of >
    while j >= 0 and arr[j] < key:
      arr[j + 1] = arr[j]
      j -= 1
      
    arr[j + 1] = key
    
  return arr

# Let's see it in action
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_desc = insertion_sort_desc(arr)
print(f"Sorted array (descending): {sorted_desc}")
# Output: Sorted array (descending): [90, 64, 34, 25, 22, 12, 11]

Sorting Custom Objects

Real-world applications often require sorting complex data structures or objects based on specific attributes. This enhanced version of insertion sort can handle any type of object and sort based on any criteria you specify. It’s incredibly flexible and can be used with custom classes, dictionaries, or any other data structure. The implementation uses a key function to determine the sorting criteria and supports both ascending and descending order.

def insertion_sort_by_key(arr, key=lambda x: x, reverse=False):
  if len(arr) <= 1:
    return arr
    
  for i in range(1, len(arr)):
    current = arr[i]
    j = i - 1
    
    while j >= 0 and (key(arr[j]) > key(current)) != reverse:
      arr[j + 1] = arr[j]
      j -= 1
      
    arr[j + 1] = current
    
  return arr

# Let's sort some student records
students = [
  {'name': 'Alice', 'age': 20},
  {'name': 'Bob', 'age': 19},
  {'name': 'Charlie', 'age': 21}
]

# Sort by age
sorted_by_age = insertion_sort_by_key(students, key=lambda x: x['age'])
print("Sorted by age:", sorted_by_age)
# Output: [{'name': 'Bob', 'age': 19}, {'name': 'Alice', 'age': 20}, {'name': 'Charlie', 'age': 21}]

# Sort by name
sorted_by_name = insertion_sort_by_key(students, key=lambda x: x['name'])
print("Sorted by name:", sorted_by_name)
# Output: [{'name': 'Alice', 'age': 20}, {'name': 'Bob', 'age': 19}, {'name': 'Charlie', 'age': 21}]

# Want it in descending order? Just set reverse=True
sorted_desc = insertion_sort_by_key(students, key=lambda x: x['age'], reverse=True)
print("Sorted by age (descending):", sorted_desc)
# Output: [{'name': 'Charlie', 'age': 21}, {'name': 'Alice', 'age': 20}, {'name': 'Bob', 'age': 19}]

What’s Next?

Now that you’ve mastered the implementation of insertion sort in Python and its various applications, you might want to deepen your understanding with these related topics: