Insertion Sort Implementation

1. The Core Idea: Sorting like Playing Cards

One of the best ways to understand insertion sort is to think about how you might sort a hand of playing cards. Imagine you're dealt cards one by one. You hold the sorted cards in your hand, and with each new card you receive, you find its correct position within your sorted hand and insert it there.

This is precisely how insertion sort works. It partitions the array into two conceptual parts: a sorted sub-array on the left and an unsorted sub-array on the right. Initially, the sorted sub-array contains only the first element (an array of one is always sorted). The algorithm then iterates through the unsorted part, picking one element at a time and "inserting" it into its correct place in the sorted sub-array.

2. A Step-by-Step Walkthrough

Let's trace the algorithm with a concrete example. Consider the array [85, 12, 59, 45, 72, 51].

1. Initial State: The sorted part is [85]. The unsorted part is [12, 59, 45, 72, 51].
2. Pass 1: Pick 12 from the unsorted part. Compare it with 85. Since 12 < 85, shift 85 one position to the right. Insert 12 into the now-empty first position. The sorted part is now [12, 85].
3. Pass 2: Pick 59. Compare it with 85. 59 < 85, so we might need to shift. Compare 59 with 12. 59 > 12, so we've found the correct spot. Shift 85 to the right and insert 59. The sorted part is [12, 59, 85].
4. Pass 3: Pick 45. Compare it with 85 (shift), then 59 (shift). 45 > 12, so we stop. Insert 45. The sorted part is [12, 45, 59, 85].

This process continues until all elements from the unsorted part have been inserted into the sorted part. The following diagram illustrates this entire process clearly.

3. The Shifting Mechanism in Code

A key detail of the implementation isn't swapping elements one by one, but rather shifting larger elements to the right to open up a space for the element we're inserting. This is a more efficient way to move data within the array for this specific algorithm.

Here's how it works in practice:

1. Store the current element you want to insert in a temporary variable (e.g., currentValue). This frees up its original position in the array.
2. Work backwards from the position just before currentValue.
3. As long as you encounter elements that are greater than currentValue, copy them one position to their right.
4. When you either reach the beginning of the array or find an element that is smaller than or equal to currentValue, you've found the insertion point.
5. Place currentValue into this now-vacant spot.

The following video provides an excellent, detailed visualization of this shifting process, which will make the Java code much easier to understand.

4. Java Implementation

Now that you have a clear picture of the logic, let's look at a clean and well-commented Java implementation. The code directly translates the shifting mechanism we just discussed.

public class InsertionSort {
    public static void sort(int[] arr) {
        // Start from the second element (arr[0] is already 'sorted')
        for (int i = 1; i < arr.length; i++) {
            // The element to be inserted into the sorted portion
            int currentValue = arr[i];
            
            // j is the index of the last element in the sorted portion
            int j = i - 1;

            // Move elements of arr[0..i-1], that are greater than currentValue,
            // to one position ahead of their current position.
            while (j >= 0 && arr[j] > currentValue) {
                arr[j + 1] = arr[j]; // Shift element to the right
                j--;
            }
            
            // Place the current value at its correct position
            arr[j + 1] = currentValue;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {85, 12, 59, 45, 72, 51};
        sort(numbers);
        System.out.println(java.util.Arrays.toString(numbers));
        // Output: [12, 45, 51, 59, 72, 85]
    }
}

Let's break down the key parts:

• Outer for loop: for (int i = 1; i < arr.length; i++). This loop iterates through the unsorted part of the array. We start at i = 1 because the first element at i = 0 is considered our initial sorted sub-array.
• currentValue: We save arr[i] before the inner loop starts overwriting array positions.
• Inner while loop: while (j >= 0 && arr[j] > currentValue). This is the core of the algorithm.
  • j >= 0: Prevents us from going out of bounds at the start of the array.
  • arr[j] > currentValue: This is the comparison that drives the shifting. We continue shifting as long as the element in the sorted part is larger than the value we're trying to insert.
• Insertion: arr[j + 1] = currentValue;. After the while loop finishes, j+1 is the correct index for currentValue.

5. Performance Analysis

Understanding an algorithm's performance is critical for technical interviews. Let's analyze insertion sort using Big O notation.

Source: Adapted from Interview Cake.

Time Complexity

• Worst Case: $O(n^2)$. This occurs when the array is sorted in reverse order. For each element, we have to shift all the elements in the sorted sub-array. The outer loop runs n times, and the inner loop also runs approximately n times in the worst case, leading to quadratic complexity.
• Best Case: $O(n)$. This happens when the array is already sorted. The outer loop still runs n-1 times, but the inner while loop's condition (arr[j] > currentValue) is immediately false for every element. So, we only perform a single comparison for each element, resulting in linear time complexity.
• Average Case: $O(n^2)$. For a randomly ordered array, we expect to insert each element somewhere in the middle of the sorted sub-array. This means, on average, the inner loop runs a number of times proportional to i (the outer loop index), which again leads to quadratic complexity.

Space Complexity

• $O(1)$. Insertion sort is an in-place algorithm. It sorts the array without requiring any significant additional memory. We only use a couple of variables (currentValue, i, j) to manage the process, regardless of the array's size. This is one of its key strengths.

Conclusion

In this lesson, you've implemented your first sorting algorithm, insertion sort. It's a foundational algorithm that provides a clear and intuitive way to think about sorting. While its quadratic time complexity makes it unsuitable for very large datasets, its simplicity, O(1) space complexity, and excellent performance on small or nearly-sorted arrays make it an important tool to have in your algorithmic toolkit.

Here are the key takeaways:

• Mechanism: Insertion sort builds a sorted sub-array by picking elements from the unsorted part and inserting them one by one into their correct position.
• Implementation: It uses a nested loop structure, where the inner loop shifts larger elements to the right to make space for the element being inserted.
• Performance: It has a best-case time complexity of $O(n)$, but an average and worst-case of $O(n^2)$. Its space complexity is $O(1)$.
• Stability: Insertion sort is a stable sort, meaning it preserves the relative order of equal elements.

In our next lesson, we will explore merge sort. This will be a significant step up in efficiency. Merge sort uses a "divide and conquer" strategy, which will bring us back to the recursive thinking you practiced in the previous lesson. You'll see how breaking a problem into halves recursively can lead to a much faster $O(n\log n)$ sorting algorithm.