Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) 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 (quite) small data sets
- Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
- More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
- Stable; i.e., does not change the relative order of elements with equal keys
- In-place; i.e., only requires a constant amount O(1) of additional memory space
- Online; i.e., can sort a list as it receives it
When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort.
Read more about Insertion Sort: Algorithm, Best, Worst, and Average Cases, Comparisons To Other Sorting Algorithms, Variants
Famous quotes containing the word sort:
“I am opposed to writing about the private lives of living authors and psychoanalyzing them while they are alive. Criticism is getting all mixed up with a combination of the Junior F.B.I.- men, discards from Freud and Jung and a sort of Columnist peep- hole and missing laundry list school.... Every young English professor sees gold in them dirty sheets now. Imagine what they can do with the soiled sheets of four legal beds by the same writer and you can see why their tongues are slavering.”
—Ernest Hemingway (1899–1961)