Sorting Comparison
In this page:
Basic Idea
With several sorting algorithms covered, the natural next question is when to actually use each one — the right choice depends on data size, how nearly-sorted the input already is, memory constraints, and whether stability (preserving the relative order of equal elements) matters.
Example: Basic Idea
#include <iostream>
using namespace std;
int main() {
cout << "The right sort depends on data size, whether it is nearly sorted, and memory constraints";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("The right sort depends on data size, whether it is nearly sorted, and memory constraints");
}
}print("The right sort depends on data size, whether it is nearly sorted, and memory constraints")#include <stdio.h>
int main() {
printf("The right sort depends on data size, whether it is nearly sorted, and memory constraints");
return 0;
}Login to try C/C++/Java code in the editor
Step by Step
Bubble, selection, and insertion sort all run in O(n²) in the worst case, but insertion sort is genuinely fast on nearly-sorted data, while bubble and selection sort don't have that advantage — for small arrays, the simplicity of any of the three is often good enough anyway.
Example: Step by Step
#include <iostream>
using namespace std;
int main() {
cout << "Bubble, selection, and insertion sort are all O(n^2) worst case; insertion sort is fastest on nearly-sorted data";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Bubble, selection, and insertion sort are all O(n^2) worst case; insertion sort is fastest on nearly-sorted data");
}
}print("Bubble, selection, and insertion sort are all O(n^2) worst case; insertion sort is fastest on nearly-sorted data")#include <stdio.h>
int main() {
printf("Bubble, selection, and insertion sort are all O(n^2) worst case; insertion sort is fastest on nearly-sorted data");
return 0;
}Login to try C/C++/Java code in the editor
Small Array
Merge sort guarantees O(n log n) in every case at the cost of extra memory, quicksort averages the same speed in-place but risks O(n²) on adversarial input, and heap sort guarantees O(n log n) with O(1) extra space but tends to be slower in practice than a well-tuned quicksort.
Example: Small Array
#include <iostream>
using namespace std;
int main() {
cout << "Merge sort guarantees O(n log n) with extra memory; quicksort averages the same speed in-place";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Merge sort guarantees O(n log n) with extra memory; quicksort averages the same speed in-place");
}
}print("Merge sort guarantees O(n log n) with extra memory; quicksort averages the same speed in-place")#include <stdio.h>
int main() {
printf("Merge sort guarantees O(n log n) with extra memory; quicksort averages the same speed in-place");
return 0;
}Login to try C/C++/Java code in the editor
Practice
Counting sort and radix sort beat the O(n log n) comparison-sort lower bound entirely, but only work for integers (or integer-like keys) within a bounded range — they're not general-purpose replacements, just faster options when your data fits their constraints.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Counting sort and radix sort beat the O(n log n) comparison-sort lower bound but only work for integer-like keys";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Counting sort and radix sort beat the O(n log n) comparison-sort lower bound but only work for integer-like keys");
}
}print("Counting sort and radix sort beat the O(n log n) comparison-sort lower bound but only work for integer-like keys")#include <stdio.h>
int main() {
printf("Counting sort and radix sort beat the O(n log n) comparison-sort lower bound but only work for integer-like keys");
return 0;
}Login to try C/C++/Java code in the editor
Summary
In practice, most language standard libraries default to a hybrid: something like quicksort or a tuned merge/insertion-sort combination that switches strategy based on input size, rather than committing to a single algorithm for every case.
Example: Summary
#include <iostream>
using namespace std;
int main() {
cout << "Most standard libraries default to a hybrid of quicksort, merge sort, and insertion sort for small runs";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Most standard libraries default to a hybrid of quicksort, merge sort, and insertion sort for small runs");
}
}print("Most standard libraries default to a hybrid of quicksort, merge sort, and insertion sort for small runs")#include <stdio.h>
int main() {
printf("Most standard libraries default to a hybrid of quicksort, merge sort, and insertion sort for small runs");
return 0;
}Login to try C/C++/Java code in the editor
- Picking an algorithm only by its best-case or average case, when quicksort can degrade to
O(n^2). - Using counting or radix sort on data that is not small integers, where they do not apply.
- Ignoring memory: merge sort needs
O(n)extra space while heap sort and quicksort are in place.
- Bubble, selection, and insertion sort are simple sorting algorithms.
- Merge, quick, and heap sort are more efficient algorithms.
- Counting and radix sort use different approaches, and a comparison helps you choose the right algorithm.
Chapter Quiz — Complete all 9 topics to unlock
0/9 topics done
Complete these topics first: