DEV Community

Cover image for Insertion Sort
CONRAD
CONRAD

Posted on

Insertion Sort

Insertion sort builds the final sorted array one item at a time by comparisons. works best on small datasets and is much less efficient than quicksort, mergesort.

My understanding on this is that insertion sort removes one item from the input array/list, finds the location it belongs within the sorted list, and inserts it there. it repeats until no input elements remain.

below is the solution, using a recursive approach:

const insertionSort = (arr, n) => {
    if(n > 0) {     //base case
        insertionSort(arr, (n - 1))

        let x = arr[n];
        let j = (n - 1);

        while (j >=0 && arr[j] > x) {
            //swap 
            arr[j+1] = arr[j];
            j = j - 1;
        }
        arr[j+1] = x;

        console.log(arr, '\n');
    }
}
const inputArr = [5,10,1,25];
insertionSort(inputArr, (inputArr.length - 1));  // [1, 5, 10, 25]
Enter fullscreen mode Exit fullscreen mode

Worst/Average case: O(n^2)
However insertion sort is the fastest in sorting small datasets, even faster than quicksort. but terrible with large datasets.

Top comments (1)

Collapse
 
janebrown profile image
JaneBrown

What are the steps of insertion sort? diamond exchange betting id