Insertion sort

Insertion sort is considered to be one of the building blocks of sorting. It has its place in real-world use cases while not being too hard to understand.

Implementation

So how does it work? Well, we basically loop over every element and insert the value at the position of the last previous that meets our condition.

So, let's take a look at a step-by-step explanation.

• We start looping through the array starting with the second element.
• We compare the second element to the first one; if it meets our condition (here if it is smaller), we swap,
• We go to the next element and again we compare it with every preceding value as long as our condition is met. When it isn't, we set the current value where it should be.

Now let's take a look at what our insertionSort function should look like:

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    for (var j = i - 1; j >= 0 && arr[j] > current; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = current;
  }
  return arr;
}

// Example:
// Initial array: [4, 3, 2]
// After first iteration: [3, 4, 2]
// After second iteration: [2, 3, 4]

Let's step through this code together:

• We first loop through every value starting at the second one (to avoid an unnecessary iteration comparing the value to itself).
• Inside this loop, we store our current value (because we will move things around).
• We loop a second time over every element that's preceding our current element (only one on the first iteration obviously, as we keep looping the subarray already sorted grows proportionally).
• At every iteration, we check if the current value meets our condition (here if it is smaller than its preceding value).
• If so, we move our preceding value one index forward (potentially overriding our current value, that's why we stored it).
• We continue this process until we find the correct position for our current value.
• Then we simply set the current value where it belongs.

Performance considerations

This algorithm involves a loop inside a loop, meaning a quadratic time complexity (Big O of n²), definitely not the best performance-wise, but as we mentioned, we always have a subarray sorted, which could be helpful if we received values gradually like from a stream.

Here are some key points to consider:

• Worst-case scenario: O(n²) In the worst-case scenario, where the array is in reverse order, insertion sort will have to perform the maximum number of comparisons and swaps. This results in a time complexity of O(n²), where n is the number of elements in the array.
• Best-case scenario: O(n) In the best-case scenario, where the array is already sorted, insertion sort will not have to swap anything, and the number of iterations is minimized, resulting in a time complexity of O(n).
• Average-case scenario: O(n²) On average, insertion sort will still require the same number of iterations and a significant number of comparisons and swaps, resulting in an average time complexity of O(n²).

Practical Use Cases

Insertion sort can be particularly useful in scenarios where the data is nearly sorted or when dealing with small datasets. It is also beneficial in situations where you receive values gradually, such as from a stream, because it can efficiently insert new elements into an already sorted sequence.

Additionally, insertion sort is often used as a part of more complex algorithms, such as Timsort, which is used in Python's sorting algorithm and Java's Arrays.sort() for non-primitive types. This hybrid sorting algorithm takes advantage of insertion sort's efficiency on small or nearly sorted datasets.

Let's consider a more realistic example where we have an array of objects, and we want to sort these objects based on a specific key. We can modify the insertionSort function to accept a second parameter, key, which specifies the property to sort by.

Here's how you can do it:

function insertionSort(arr, key) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j][key] > current[key]) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

// Example usage:
const data = [
  { name: 'Alice', age: 30 },
  { name: 'Bob', age: 25 },
  { name: 'Charlie', age: 35 }
];

insertionSort(data, 'age');
// [
//   { name: 'Bob', age: 25 },
//   { name: 'Alice', age: 30 },
//   { name: 'Charlie', age: 35 }
// ]

In this example, the insertionSort function sorts the array of objects based on the age property. The key parameter allows you to specify any property of the objects to sort by, making the function more flexible and reusable.

Conclusion

Insertion sort is a fundamental sorting algorithm that is easy to understand and implement. While it may not be the most efficient for large datasets due to its quadratic time complexity, it shines in scenarios where the data is nearly sorted or when dealing with small datasets. Its ability to sort data incrementally makes it particularly useful for streaming data or as a component in more complex sorting algorithms.