Comparison of Sorting Algorithms
Discover a wealth of knowledge on sorting algorithms: explore usage scenarios, gain insights into time and space complexity
Algorithm Name |
When to Use |
Time Complexity (Worst Case) |
Space Complexity (Worst Case) |
Small input size, partially sorted or nearly sorted lists |
O(n^2) |
O(1) |
|
Large input size, need for stable sorting order |
O(n log n) |
O(n) |
|
Small input size, simplicity and ease of implementation |
O(n^2) |
O(1) |
|
Finding maximum subarray in an array |
O(n log n) |
O(log n) |
|
Multiplying large matrices |
O(n^log2(7)) |
O(n^log2(7)) |
|
Selecting the best candidate from a pool of applicants |
O(n) |
O(1) |
|
Efficiently sorting large data sets, maintaining a minimum heap property |
O(n log n) |
O(1) |
|
Efficiently sorting large data sets, maintaining a maximum heap property |
O(n log n) |
O(1) |
|
General-purpose sorting, average case performance is good |
O(n^2) |
O(n) |
|
General-purpose sorting, efficient for many types of data |
O(n^2) |
O(log n) |
|
Sorting with uncertainty or tolerance in comparisons |
O(n^2) |
O(1) |
|
Sorting non-negative integers with a small range of values |
O(n + k) |
O(n + k) |
|
Sorting integers or strings with fixed lengths or bounded range |
O(d * (n + k)) |
O(n + k) |
|
Sorting uniformly distributed floating-point numbers or integers |
O(n^2) (worst) |
O(n) |
|
Simple sorting with minimal memory usage |
O(n^2) |
O(1) |
|
Simple sorting with minimal memory usage |
O(n^2) |
O(1) |
|
Sorting small positive integers |
O(n^2) |
O(n) |
|
Sorting in parallel or with limited memory |
O(log^2(n)) |
O(log^2(n)) |
|
Sorting large data sets with limited memory and stable sorting order |
O(n log n) |
O(n) |
|
Simple sorting with bidirectional passes |
O(n^2) |
O(1) |
|
Simple sorting with improved bubble sort performance |
O(n^2) |
O(1) |
|
Sorting multidimensional arrays or matrices |
O(n log n) |
O(n) |
|
Sorting with minimal write operations |
O(n^2) |
O(1) |
|
Simple sorting with ease of implementation and minimal memory usage |
O(n^2) |
O(1) |
|
Sorting large data sets, stable sorting order |
O(n log n) |
O(n) |
|
Sorting small to moderate-sized lists |
O(n^2) |
O(1) |
|
Sorting lists with variable-length or complex records |
O(n log n) |
O(n) |
|
Sorting when the range of values is known |
O(n + k) |
O(k) |
|
General-purpose sorting, moderately large data sets |
O(n log n) (worst) |
O(1) |
|
Large data sets, partially sorted or nearly sorted |
O(n log n) |
O(1) |
|
Sorting large data sets, need for stable sorting |
O(n log n) |
O(n) |