Insertion Sort with Reverse Thinking

In the previous article Problems Faced by Selection Sort, we analyzed several issues encountered by selection sort. We then gradually optimized it to develop Bubble Sort, which provides stability to the sorting algorithm and allows it to terminate early when the input array is highly ordered, thus improving efficiency.

To recap, the key to bubble sort lies in optimizing the following segment of code:

// perform the first optimization on selection sort to achieve stability
void sort(int[] nums) {
    int n = nums.length;
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // find the minimum value nums[minIndex] in the unsorted part
        int minIndex = sortedIndex;
        for (int i = sortedIndex + 1; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }

        // insert nums[minIndex] into the position of nums[sortedIndex]
        // shift the elements from nums[sortedIndex..minIndex] one position back
        int minVal = nums[minIndex];
        // array data moving operation
        for (int i = minIndex; i > sortedIndex; i--) {
            // swap(nums[i], nums[i - 1])
            nums[i] = nums[i - 1];
        }
        nums[sortedIndex] = minVal;

        sortedIndex++;
    }
}

To avoid having two for loops inside a while loop, we use a bubble-like method to gradually swap the reverse pairs in nums[sortedIndex..], placing the smallest value at nums[sortedIndex].

Okay, let's pause here. Forget about the optimization methods for bubble sort, and consider whether there are other ways to optimize the above code by reducing the two for loops within the while loop into a single for loop.

Reverse Thinking

The algorithm described above finds the smallest value in nums[sortedIndex..] and inserts it into the position nums[sortedIndex].

But can we think in reverse? In the sorted portion of the array nums[0..sortedIndex-1], can we find the correct position for nums[sortedIndex] and insert it there?

Back when I was considering how to optimize insertion sort, I thought about this approach because I wanted to take advantage of the array's order. Since nums[0..sortedIndex-1] is already sorted, I could use binary search to find the position where nums[sortedIndex] should be inserted.

In this way, the first inner for loop in the above code could be optimized to logarithmic complexity.

However, thinking it over, using binary search seems unnecessary. Even if I find the insertion position for nums[sortedIndex] using binary search, I still need to move the elements to insert it. This would not be simpler or more efficient than just iterating through and swapping elements:

// further optimize selection sort by inserting elements into the left sorted array
// this algorithm has another name, called insertion sort
void sort(int[] nums) {
    int n = nums.length;
    // maintain [0, sortedIndex) as a sorted array
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // insert nums[sortedIndex] into the sorted array [0, sortedIndex)
        for (int i = sortedIndex; i > 0; i--) {
            if (nums[i] < nums[i - 1]) {
                // swap(nums[i], nums[i - 1])
                int tmp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = tmp;
            } else {
                break;
            }
        }
        sortedIndex++;
    }
}

The Higher the Initial Order, the Better the Efficiency

Clearly, the efficiency of insertion sort is highly related to the order of the input array. Extreme examples can help with understanding:

If the input array is already sorted, or only a few elements are out of order, the inner for loop of insertion sort hardly needs to perform any element swaps, making the time complexity approach $O(n)$.

If the input array is completely reversed, the efficiency of insertion sort will be very low, with the inner for loop having to swap all elements in nums[0..sortedIndex-1] each time, resulting in a total time complexity approaching $O(n^2)$.

Compared to bubble sort, the overall performance of insertion sort should be higher than that of bubble sort.

Intuitively, the inner for loop of insertion sort only needs to traverse and swap elements in the ordered part nums[0..sortedIndex-1] to the left of sortedIndex. In most non-extreme cases, it may not need to traverse all elements in nums[0..sortedIndex-1]; whereas the inner for loop of bubble sort needs to traverse all elements in nums[sortedIndex..] to the right of sortedIndex each time.

Therefore, the number of operations for bubble sort is approximately $n^2/2$, while the number of operations for insertion sort is less than $n^2/2$.

You can submit the insertion sort code to LeetCode Problem 912 "Sort an Array", and it may still time out, but it can demonstrate that the logic of the algorithm code is correct. In future articles, we will continue to explore how to optimize sorting algorithms.