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++;
    }
}

Higher Initial Order Leads to Higher Efficiency

Clearly, the efficiency of insertion sort is closely related to the initial order of the input array. Consider extreme examples to understand this:

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, so the time complexity approaches $O(n)$.

If the input array is completely reversed, the efficiency of insertion sort becomes very low, as the inner for loop must swap all elements in nums[0..sortedIndex-1] each time, making the total time complexity close to $O(n^2)$.

Comparing insertion sort with bubble sort, the overall performance of insertion sort should be better than bubble sort.

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

Therefore, the operation count for bubble sort is about $n^2/2$, while the operation count for insertion sort is less than $n^2/2$.

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