Which stable, in-place sorting algorithm with a worst-case complexity of O(n^2) works by repeatedly taking the next element and placing it into its correct position among the already-sorted elements?
Show answer
Insertion sort
Insertion sort is highly efficient for small datasets or nearly sorted arrays. While its worst-case is quadratic, it is stable (preserving the relative order of equal elements) and requires only O(1) auxiliary space.
Also asked as:
- Which O(n^2) sorting algorithm is stable, in-place, and builds the final sorted array one item at a time by inserting each new element into its proper location?