Insertion Sort – Algorithm, Implementation and Performance

The insertion sort algorithm internally divides an array into two parts: sorted and unsorted. Initially, the sorted part only contains the first element of the list, and the unsorted part contains all the remaining elements. The algorithm functions by inserting an element from an unsorted array to its correct position in a sorted array.

This insertion sort tutorial will provide an in-depth exploration of its algorithm, complexity, and implementation in Java. Additionally, we will explore some of the key advantages and disadvantages of the insertion sort.

1. Insertion Sort Algorithm

During each iteration of the insertion sort, the algorithm chooses the first element of the unsorted array and compares it to the elements in the sorted part. If we find a comparatively greater element, we shift it up one position until we reach the correct position for the selected element. We repeat this process for each element in the unsorted part until we sort the entire list.

Now, let’s understand the step-by-step process of the insertion sort algorithm.

1. Take an array of n unsorted elements.
2. Begin by selecting the second element in the array and comparing it to the first element. If the second element is less than the first, swap them.
3. Next, examine the third element in the array and compare it to the second element. If the third element is less than the second, swap them. Otherwise, if the third element is equal to or greater than the second element, leave it in its current position.
4. Continue to perform step 3 for each element in the array until you reach the final element.
5. Once you properly position the final element, the array will partially sort, and the smallest element will be at the beginning of the array.
6. Proceed to the second element in the array and compare it to the first element. If the second element is less than the first, swap them.
7. Continue performing step 6 on each element in the partially sorted array until you reach the final element.
8. Repeat steps 5 to 7 until you have sorted the entire array.

After the whole process, the array is sorted.

2. Insertion Sort In Action

Now, let’s move on to an example and understand how it works.

Let us take an array [13, 12, 14, 6, 7].

1st Iteration:

First, compare the array’s first two elements and then swap them according to their values.

In this case, we find that 13 is greater than 12, indicating that the elements are not in sorted order and that 13 is in the incorrect position. Therefore, the algorithm swaps the positions of 12 and 13 and places 12 in the sorted sub-array.

2nd Iteration:

The sorted array contains two elements:12 and 13. Now let’s move on to the next two elements in the array and compare them according to their values.

Here, the elements are already in sorted order with 14 being greater than 13, indicating that no swap is needed.

3rd Iteration:

The sorted array contains three elements:12, 13 and 14. In the 3rd iteration here, let’s move on to the next two elements which are 14 and 6 in the array, and compare them according to their values.

In this case, we find that 14 is greater than 6, indicating that the elements are not in sorted order and that 6 is in the incorrect position. Therefore, the algorithm performs a swap between the positions of 14 and 6.

But as we can see that after swapping 6 and 13 are not in their correct order therefore, the algorithm performs a swap between the positions of 6 and 13.

Now again as we can see that after swapping, 12 and 6 are not in their correct order therefore, the algorithm performs a swap between the positions of 12 and 6. Now after swapping the array will look like this:

After this 3rd iteration now 6 is at its correct position.

4th Iteration:

Now 6, 12, and 13 are present in the sorted sub-array. Let’s move on to the next two elements which are 14 and 7 in the array, and compare them according to their values.

It’s clear from the above array that 7 and 14 are not in sorted order so swap them.

Swap 13 and 7 again because they are not in the sorted order.

Still, 7 is not in its correct position because 12 is greater than 7, hence swap 12 and 7 again. The final sorted array looks like this:

Now finally the array is completely sorted.

3. Implementation of Insertion Sort in Java

Let us hit the keyboard and write a program demonstrating how to implement insertion sort in Java.

3.1. Sort

The insertion_sort() function accepts an integer array “arr“. This function first calculates the length of the array “arr” that is n. It then iterates through the array from the second element (i = 1) to the last element (i = n-1), and for each element arr[i], it compares it to the previous elements (arr[i-1], arr[i-2], arr[i-3], …, arr[0]) in reverse order until it finds the correct position for arr[i] in the sorted sequence.

To achieve this, the insertion_sort() function uses the variable “key” to temporarily store the value of arr[i] and the variable j to keep track of the position of the last element that is greater than the key. It then shifts all the elements that are greater than the key one position to the right (arr[j+1] = arr[j]), until it finds the correct position for the key, which is arr[j+1].

After the inner while loop completes, arr[j+1] is set to the key, which means that the key is inserted at its correct position in the sorted sequence. This process repeats until all elements in the array are sorted.

void insertion_sort(int arr[]) {
  int n = arr.length;

  // loop for each iteration
  for (int i = 1; i < n; i++) {

    // storing value of arr[i] in key temporarily
    int key = arr[i];
    int j = i - 1;

    // Move all the elements to the right side of the key which are greater than key value.
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}

3.2. Demo

Let us combine both functions and run the program to verify the output.

int arr[] = {13, 12, 14, 6, 7};
System.out.println("Original Array: " + Arrays.toString(arr));

InsertionSort insertionSort = new InsertionSort();

insertionSort.insertion_sort(arr);
System.out.println("\nSorted array: " + Arrays.toString(arr));

The program output:

Original Array: [13, 12, 14, 6, 7]

Sorted array: [6, 7, 12, 13, 14]

4. Insertion Sort Performance Improvement

If we look at the previous implementation then we can quickly identify that iterating over the array and finding the correct spot inside an already sorted array seems the most time taking task and can easily be improved using a more fast search algorithm.

When we identify that array may be sorted already, we can employ binary search algorithm which is more effective for already sorted arrays. So our improved insertion sort algorithm will become:

@SuppressWarnings({ "rawtypes", "unchecked" })
void insertionSortImproved(int[] arr) {

  for (int i = 1; i < arr.length; i++) {

    int key = arr[i];
    int jLeft = 0;
    int jRight = i - 1;

    //Check if its current position is in correct position
    if (((Comparable) arr[jRight]).compareTo(key) > 0) {

      //Perform binary search
      while (jRight - jLeft >= 2) {
        int jMiddle = (jRight - jLeft) / 2 + jLeft - 1;
        if (((Comparable) arr[jMiddle]).compareTo(key) > 0) {
          jRight = jMiddle;
        } else {
          jLeft = jMiddle + 1;
        }
      }

      if (jRight - jLeft == 1) {
        int jMiddle = jLeft;
        if (((Comparable) arr[jMiddle]).compareTo(key) > 0) {
          jRight = jMiddle;
        } else {
          jLeft = jMiddle + 1;
        }
      }
      
      //Place the element
      int j = i;
      for (j = i; j > jLeft; j--) {
        arr[j] = arr[j - 1];
      }
      arr[j] = key;
    }
  }
}

5. Time and Space Complexity of Insertion Sort

5.1. Time Complexity

In the worst-case scenario, insertion sort exhibits a time complexity of O(n^2) when sorting an array with n elements.

Here in the best-case scenario, where the input array is already sorted, the algorithm will have a time complexity of O(n), because it only needs to make n-1 comparisons and no swaps are done.

In the average-case scenario, the number of comparisons and swaps required to sort the array will rely on the distribution of the elements within it, but the average time complexity is still O(n^2).

5.2. Space Complexity

Insertion sort has a space complexity of O(1), indicating that it uses a fixed amount of memory that remains constant, regardless of the size of the input array.

By sorting the input array in place, the algorithm avoids employing additional data structures or generating new arrays. Only a few variables are necessary to keep track of the location of elements and store values temporarily during swaps.

6. Advantages and Disadvantages

6.1. Advantages

• Efficiency for small arrays: Due to its low overhead and minimal need for comparisons and swaps, insertion sort is particularly effective when applied to small arrays. In fact, for arrays containing fewer than 10 elements, insertion sort may outperform more complex algorithms such as quicksort or merge sort.
• Adaptive: Being adaptive, insertion sort has the ability to optimize its performance when presented with an input array that is already partially sorted. By leveraging the existing order of the elements in the array, insertion sort is able to reduce the number of comparisons and swaps required to complete the sorting process.
• Stable: As a stable sorting algorithm, insertion sort maintains the relative position of equivalent elements in the sorted array. This feature is critical in certain use cases that necessitate maintaining the order of equal elements.
• In-place sorting: The in-place sorting mechanism of insertion sort eliminates the need for additional memory or data structures, making it a suitable option when memory usage is a concern or when working with large datasets that may exceed memory capacity.
• Easy implementation: With its straightforward implementation and minimal code requirements, insertion sort is an ideal choice for educational purposes or situations where the readability and maintainability of code are required.

6.2 Disadvantages

• Time complexity: Insertion sort exhibits a time complexity of O(n^2), which makes it unsuitable for processing large arrays or datasets.
• Limited scalability: Due to its inability to take advantage of contemporary hardware architectures such as caching or pipelining, insertion sort exhibits limited scalability. Consequently, when applied to extremely large datasets, it may not perform well compared to other sorting algorithms.
• Not for certain types of data: Insertion sort may not be an optimal choice for specific data types such as linked lists or data structures that exhibit poor random access performance. This is due to the algorithm’s frequent need for arbitrary access to elements in the input array.

7. Conclusion

To summarize, insertion sort represents a straightforward algorithm for sorting small arrays or datasets. It offers several advantages over other sorting algorithms. These advantages include adaptiveness, stability, efficiency for small arrays, in-place sorting, and ease of implementation.

Overall, insertion sort is an excellent option for scenarios where the input array is partially sorted or when memory usage is a significant factor. However, for larger arrays or datasets, algorithms such as quicksort or mergesort may be better suited to the task.

Happy Learning !!

Sourcecode on Github