Insertion Sort in JavaScript

1. Sort Techniques in JavaScript
2. Implement the Insertion Sort Technique in JavaScript

This article will discuss the idea of the Insertion Sort in JavaScript and provide an example of its implementation.

Sort Techniques in JavaScript

A whole bunch of sorting techniques was developed by interested individuals with the vision to ensure optimality, acceleration, and fewer spacings. In this run, the insertion sort shows the worst-case time complexity is O(n^2), whereas the best case is O(n).

For a small amount of data to sort, Array.prototype.sort() is a good choice. As the preferable situation, it gives time complexity of O(n), which is better than O(n*logn).

However, the sort() function does not perform well for a huge data pile with complex objects, etc. The Array.prototype.sort() function has the implementation of the insertion sort, and thus the JavaScript default sorting algorithm is not in the efficient category.

It should also be noted that the performance of sorting a code depends upon which browser the user is using. The Chrome V8 uses the Tim Sort (Insertion Sort + Merge Sort), and Firefox uses the basic Merge Sort.

In real life scenario, raw data are not necessarily unordered. Instead, they follow a pattern of order. So, you can say that the data do not need to be sorted from scratch.

For the V8, the array is initially divided into blocks referred to as run. These runs in the bottom level are sorted with the insertion sort principle and later merged with the merge sort’s way.

If you are working with a few numbers or objects, then the Tim Sort will behave as an Insertion Sort with time complexity of O(n). Whereas in the case of large data, the V8 Sort will work as a Merge Sort with the time complexity of O(n*logn).

So, Tim Sort is a highly optimized, stable sorting technique than the traditional Merge Sort.

In our example section, we will cover the basic idea of an Insertion Sort and let you determine why it has its constraints and why it might be better than many. The discussion from the previous portion describes how the insertion sort is used in the V8 engine as it is a JavaScript engine.

Let’s hop on to the demonstration.

Implement the Insertion Sort Technique in JavaScript

The basic idea of this sort can be compared to sorting a hand of cards. We initially set a card as the first and later select the next cards to sort, referred to as the first set card.

Here, the next card is named as key, and when the key is greater than the first card, then we keep it as it is; else, we swap the position of the key and the first card. And this repeats till the entire array is traversed and sorted.

Let’s check the code lines.

Code Snippet:

var arr = [4, 2, 3, 1, 7];
var size = arr.length;
for (var i = 1; i < size; i++) {
  var key = arr[i];
var j = i - 1;
  while (key < arr[j] && j >= 0) {
    arr[j + 1] = arr[j]
    j--
  }
  arr[j + 1] = key
}
console.log(arr)

Output:

As we can see, the Insertion Sort has a space complexity of O(1) as it does not occupy any other array of spaces to store the key rather than the 1 slot. So, if you are conscious about optimal space, this sort might fit well.