# 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 $O(1)$, making it an in-place sorting algorithm. Its time complexity is $O(n^2)$, similar to selection sort, as it involves an arithmetic series summation, approximately $n^2/2$ 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 $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.