Insertion Sort with Reverse Thinking
Prerequisites
Before reading this article, you should first learn:
Summary in One Sentence
Insertion sort is an optimization based on Selection Sort, where nums[sortedIndex]
is inserted into the sorted array on the left. It is particularly efficient for arrays that are already mostly sorted.
In the previous article Challenges Faced by Selection Sort, we analyzed several issues with selection sort and gradually optimized it to develop Bubble Sort. This led to a sorting algorithm with stability that can terminate early when the input array is mostly sorted, thereby increasing efficiency.
To recap, the key point of bubble sort lies in the optimization of the following code segment:
// 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++;
}
}
Insertion Sort
This algorithm is known as Insertion Sort. Its execution process is similar to inserting a newly drawn card into a hand of already sorted cards.
Insertion sort has a space complexity of , making it an in-place sorting algorithm. Its time complexity is , similar to selection sort, as it involves an arithmetic series summation, approximately operations.
Insertion sort is a stable sorting algorithm because elements are only swapped when nums[i] < nums[i - 1]
, so the relative order of identical elements remains unchanged.
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 .
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 .
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 , while the operation count for insertion sort is less than .
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.