Cocktail Shaker Sort
Bidirectional bubble sort that traverses in both directions.
Builds the sorted array one element at a time by inserting into the correct position.
Insertion Sort builds the sorted array one element at a time by repeatedly picking the next unsorted element and inserting it into its correct position within the already-sorted portion. It works the way many people naturally sort playing cards -- picking up each card and sliding it into the right place among the cards already held in their hand. This intuitive approach makes Insertion Sort one of the most natural and easy-to-understand sorting algorithms.
Insertion Sort is one of the oldest sorting techniques, predating electronic computers. The method mirrors how humans have organized physical objects for centuries. In the context of computer science, it was among the first algorithms to be formally analyzed. Its simplicity and adaptive behavior have kept it relevant despite the development of asymptotically faster algorithms. Today, Insertion Sort plays a critical supporting role in many high-performance sorting implementations as the base case for small sub-arrays.
Note that Insertion Sort uses shifts rather than swaps. Instead of swapping the key with each larger neighbor (which would require three assignments per swap), it saves the key, shifts larger elements in bulk, and writes the key once. This makes it more efficient in practice than algorithms like Bubble Sort that rely on adjacent swaps.
| Case | Time | Space |
|---|---|---|
| Best | O(n) | O(1) |
| Average | O(n^2) | O(1) |
| Worst | O(n^2) | O(1) |
The best case of O(n) occurs when the array is already sorted -- each element is compared once with its predecessor and no shifts are needed. The worst case occurs when the array is reverse-sorted, requiring the maximum number of shifts. The number of comparisons is directly related to the number of inversions (pairs of elements in the wrong order) in the input, making Insertion Sort adaptive: the closer the input is to being sorted, the faster it runs.
The running time of Insertion Sort is O(n + d), where d is the number of inversions in the input. An inversion is a pair (i, j) where i < j but array[i] > array[j]. A fully sorted array has zero inversions and is sorted in O(n). A reverse-sorted array has n(n-1)/2 inversions and takes O(n^2). This makes Insertion Sort one of the most adaptive simple sorting algorithms -- its performance naturally improves as the input becomes more ordered.
Insertion Sort's low overhead on small inputs makes it the preferred base case for many recursive sorting algorithms. Python's Timsort uses Insertion Sort (specifically, binary insertion sort) for short runs. Java's dual-pivot Quick Sort switches to Insertion Sort for sub-arrays smaller than 47 elements. C++'s Introsort implementations typically switch to Insertion Sort below 16-32 elements. The crossover point varies by implementation, but the principle is the same: the constant factors of O(n log n) algorithms make them slower than Insertion Sort for small n.
Insertion Sort has three valuable properties. It is stable: equal elements maintain their original relative order. It is in-place: it requires only O(1) extra memory beyond the input array. And it is online: it can sort a sequence as elements arrive one at a time, without needing access to the entire input upfront. This online property makes it suitable for streaming applications.
Use Insertion Sort for small arrays (typically fewer than 50 elements), for nearly sorted data, or as the base case within a larger hybrid sorting algorithm. For general-purpose sorting of larger datasets, Merge Sort, Quick Sort, or Timsort are more appropriate.