Fundamental Algorithms8 sections · 291 units
Open in Course

Comparison Sort Summary

When to use each comparison-based sort.

SortTime (avg)Time (worst)SpaceStable
SelectionO(n2)O(n^2)O(n2)O(n^2)O(1)O(1)No
InsertionO(n2)O(n^2)O(n2)O(n^2)O(1)O(1)Yes
MergeO(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(n)O(n)Yes
QuickO(nlog⁡n)O(n \log n)O(n2)O(n^2)O(log⁡n)O(\log n)No

Use insertion sort for small arrays or nearly-sorted data. Use merge sort when stability matters or you need guaranteed O(nlog⁡n)O(n \log n). Use quicksort for general purpose (with randomization).