Class InsertionSort<T>

InsertionSort 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:

• Simple implementation
• Efficient for small data sets
• Adaptive: efficient for data sets that are already substantially sorted
• Stable: does not change the relative order of elements with equal keys
• In-place: only requires a constant amount O(1) of additional memory space

The algorithm iterates through the input array, growing the sorted array behind it. At each iteration, it removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

The worst-case time complexity is O(n^2), the average-case time complexity is O(n^2), and the best-case time complexity is O(n) when the array is already sorted.

Example

const insertionSort = new InsertionSort([3, 4, 1]);
insertionSort.sort(); // returns new array with [1, 3, 4]
// or
InsertionSort.sort([3, 4, 1]); // returns new array with [1, 3, 4]
Copy

Example

const insertionSort = new InsertionSort(
 ['alice', 'bob', 'charlie', 'alex', 'gavin'],
 (a : string, b : string) => a.localeCompare(b)
);
insertionSort.sort(); // returns new array with ['alex', 'alice', 'bob', 'charlie', 'gavin']
Copy