Insertion Sort
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:
### How it works: 1. Assume the first element is already sorted. 2. Take the next element and store it as a `key`. 3. Compare the `key` with all elements in the sorted sublist (from right to left). 4. Shift all elements that are greater than the `key` to the right by one position. 5. Insert the `key` into its correct position. 6. Repeat until the array is completely sorted.
Insertion sort is efficient for (quite) small data sets, much like other quadratic sorting algorithms. More importantly, it is adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is `O(kn)` when each element in the input is no more than `k` places away from its sorted position.
### How it works: 1. Assume the first element is already sorted. 2. Take the next element and store it as a `key`. 3. Compare the `key` with all elements in the sorted sublist (from right to left). 4. Shift all elements that are greater than the `key` to the right by one position. 5. Insert the `key` into its correct position. 6. Repeat until the array is completely sorted.
Insertion sort is efficient for (quite) small data sets, much like other quadratic sorting algorithms. More importantly, it is adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is `O(kn)` when each element in the input is no more than `k` places away from its sorted position.
Constraints
- 1 <= array.length <= 10^4
- -10^9 <= array[i] <= 10^9
TimeO(O(n²))
SpaceO(O(1))
Ready to startStep 0 / 0
TypeScript