Input: A sequence of ‘n’ numbers. [a(1),a(2),...a(n)]

Output: A permutation (reordering) of the input sequence such that [a(1)<=a(2)<=...a(n)]

Insertion is a good algorithm for sorting a small number of elements.

  • Our function takes an array and the length ‘n’ of the array.
  • Compares our current element(key) to its predecessor.
  • If our key element value is less than its predecessor, we compare it to the elements before, moving greater elements one position up to create an available index for the swapped element.

Insertion Sort Psuedocode
Photo by Thomas H. Cormen, Instructor's manual for introduction to algorithms

Implementation In JavaScript

let insertionSort = function(arr, n){
let i, key, j;
for (i = 1; i < n; i++){
// Current element
key = arr[i];
// Predecessor
j = i - 1;
// Move elements one position ahead of their current index that is greater than key
while(j >= 0 && arr[j] > key){
arr[j + 1] = arr[j];
j = j - 1
}
// Move key into the proper evaluated position
arr[j + 1] = key;
}
return arr;
}
let arr = [21,17,3,11,6];
let n = arr.length;
insertionSort(arr, n);
// Result: [ 3, 6, 11, 17, 21 ]

Maintenance

The inner ‘while’ loop works by moving preceding elements one position forward, opening the correct position for ‘key.’ Due to our loop condition, the loop can execute more than once when our’ while’ loop exits.

Termination

The outer for loop ends when i = n, the array’s length.

Implementation In python

def insertionSort(arr):
# Traverse 1 through len(arr)
for i in range(1, len(arr)):
#Ccurrent element
key = arr[i]
# Predecessor
j = i - 1
# Move elements one position ahead of their current index that is greater than key
while j >= 0 and arr[j] > key :
arr[j + 1] = arr[j]
j -= 1
# Move key into the proper evaluated position
arr[j + 1] = key
return arr
arr = [21,17,3,11,6]
insertionSort(arr)
# Result: [ 3, 6, 11, 17, 21 ]

Demo with Steps

Code Demo w/ Steps

Conclusion

Insertion sort is an incremental algorithm with an O(n^2) time complexity. Instructions are executed one after the other with no concurrent operations.

Boundary Cases

Best case: The input array elements are already sorted. Worst case: Maximum time to sort when our input array is sorted in reverse order.

Related Posts

Asynonymous
Copyright © 2025 Asynonymo.us All Rights Reserved.

Quick Links

Legal Stuff

Social Media