Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time.
It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
- It is efficient for small data sets or nearly sorted data.
- It is an in-place sorting algorithm, meaning it does not require any additional memory.
- It is stable, meaning it maintains the relative order of equal elements.
- Worst Case: O(n^2)
- Best Case: O(n)
- Average Case: O(n^2)
- Worst Case: O(1)
define insertionSort(array)
for i = 1 to array.length
current = array[i]
while i >= 0 and array[i - 1] > current
array[i] = array[i - 1]
i = i - 1
array[i] = current
return array
Image from geeksforgeeks.org
- When the input size is small or the list is nearly sorted
- When simplicity and ease of implementation is more important than efficiency.
- When you want a sorting algorithm that uses a small amount of additional memory.
Note: Insertion sort has poor performance compared to other sorting algorithms and is not recommended for large or complex lists.