Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Insertion sort	n	n2	n2	1	Yes

References

• trekhleb/javascript-algorithms
• Wikipedia

Implementations

• Python
• JavaScript

• 1
  # TODO: Implement in Python
  

• 1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  console.log(`original array = [${D.join(', ')}]`);
  
  for (let i = 1; i < D.length; i++) {
    const key = D[i];
    
    let j;
    for (j = i - 1; (j >= 0) && (D[j] > key); j--) {
      D[j + 1] = D[j];
      
    }
    D[j + 1] = key;
    
  }
  
  console.log(`sorted array = [${D.join(', ')}]`);