Learn how to implement recursive insertion sort algorithm in javascript.
Insertion sort is one of the most simplest sorting algorithm which sorts the elements by arranging the most smallest at first place, second smallest at second place and so on.
Example
Input: [1, 8, 2, 4, 5] Output: [1, 2, 4, 5, 8]
Check out the following image for better understanding of working of insertion sort.
Implementation of recursive insertion sort in javascript.
- We are going to mimic the Iterative Insertion sort in the recursive implementation.
- We will create a function which will take the array and current index as input.
- In this function we will iterate through all the elements less than the current index and swap the elements based on the sorting order.
- If the index is less than 1 then will terminate the recursive function. Else we will call the same function recursively with one index less.
//Recursive insertion sort
let recursiveInsertionSort = (arr, i = arr.length) => {
//if index is less than 1 then return
if(i <= 1){
return;
}
//Recursively call the same function
recursiveInsertionSort(arr, i - 1);
let key = arr[i - 1];
let j = i - 2;
//Sort the array
while(j >= 0 && arr[j] > key){
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
Input: let arr = [1, 8, 2, 4, 5]; recursiveInsertionSort(arr); console.log(arr); Output: [1, 2, 4, 5, 8]
Time complexity: O(n * n).
Space complexity: O(n).
Time and Space complexity.
- We are calling the same function recursively for (n – 1) elements and in each call we are iterating for all the elements less than the current index, so Time complexity is O(n * n).
- As we are calling the function recursively for (n – 1) elements, It will be stored in the call stack, so Space complexity is O(n).