Insertion sort
This is a non-optimal straightforward sorting algorithm for typical uses case but can get linear time for nearly-sorted lists. The algorithm works by keeping track of the unsorted and the sorted portions and inserting an unsorted element in the correct spot of the sorted list each time.
| Pros |
Cons |
| Stable, in-place, and online algorithm |
Quadratic worst case time complexity |
| Linear best-case performance for nearly-sorted lists |
|
| More efficient (factor-wise) than other quadratic comparison algorithms |
|
LeetCode Problems
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
