DSA04 - meron-401n14/seattle-javascript-401n14 GitHub Wiki

Insertion Sort

Insertion sort is 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, However insertion sort provides several advantages:

• Simple implementation
• Efficient for (quite) small data sets
• More efficient in practice than most other simple quadratic algorithms such as selection sort or bubble sort
• Adaptive. i.e efficient for data sets that already substantially sorted
• Stable; i.e does not change the relative order of elements with equal keys
• In-place; i.e only requires a constant amount O(1) of additional memory space
• Online; i.e can sort a list as it receives it ``

Pseudocode

i ← 1 while i < length(A) j ← i while j > 0 and A[j-1] > A[j] swap A[j] and A[j-1] j ← j - 1 end while i ← i + 1 end while