Insertion Sort

This article introduces the insertion sort algorithm—a straightforward and intuitive sorting method used to arrange elements in a list.

Definition

Insertion sort works by dividing the list into two parts: a sorted section and an unsorted section. Initially, the sorted section contains just the first element. Then, each subsequent element from the unsorted section is taken and inserted into its correct position within the sorted section. This method is very similar to how one might organize a hand of cards: you pick up a card from the table and insert it into your hand in the right order based on its value.

Imagine watching a demonstration where each element (or card) is gradually inserted into its proper spot until the entire list is sorted.

Properties

Stability

Insertion sort is a stable sorting algorithm, which means that when two elements have equal values, their original order is maintained in the sorted list.

Time Complexity

The best-case time complexity is $O(n)$ , which occurs when the list is already nearly sorted.
In the worst and average cases, the time complexity is $O(n^2)$ .

Code Implementation

Pseudocode

Below is the pseudocode for insertion sort expressed in a mathematical format:

\begin{array}{ll} 1 & \textbf{Input: } \text{An array } A \text{ with } n \text{ elements.} \\ 2 & \textbf{Output: } A \text{ sorted in non-decreasing order (stable).} \\ 3 & \textbf{Method: } \\ 4 & \textbf{for } i \gets 2 \textbf{ to } n \\ 5 & \quad key \gets A[i] \\ 6 & \quad j \gets i-1 \\ 7 & \quad \textbf{while } j > 0 \textbf{ and } A[j] > key \\ 8 & \quad\quad A[j+1] \gets A[j] \\ 9 & \quad\quad j \gets j - 1 \\ 10 & \quad A[j+1] \gets key \end{array}

Python Implementation

Here is a simple Python implementation of insertion sort:

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
 
# Example usage:
if __name__ == "__main__":
    data = [34, 8, 64, 51, 32, 21]
    insertion_sort(data)
    print("Sorted array:", data)

Binary Insertion Sort

Binary insertion sort enhances the standard insertion sort by utilizing binary search to locate the correct insertion position. This optimization is particularly useful when the sorted portion is large, as it reduces the number of comparisons needed. However, note that while the constant factors are improved, the overall time complexity remains $O(n^2)$ due to the shifting of elements.

Python Implementation for Binary Insertion Sort

def binary_search(arr, key, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] < key:
            start = mid + 1
        else:
            end = mid - 1
    return start
 
def binary_insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        # Find the correct position to insert key using binary search
        pos = binary_search(arr, key, 0, i - 1)
        # Shift elements to make room for key
        arr[pos+1:i+1] = arr[pos:i]
        arr[pos] = key
 
# Example usage:
if __name__ == "__main__":
    data = [34, 8, 64, 51, 32, 21]
    binary_insertion_sort(data)
    print("Sorted array:", data)

By learning and experimenting with these implementations, you'll gain a solid understanding of how insertion sort works and how binary search can be used to optimize the insertion process. Enjoy your coding journey!

Heapsort Merge Sort