Data Structure Sorting: Types and Examples Explained in Detail
Sorting is the process of arranging data in a particular order — typically ascending or descending. Different sorting algorithms make different trade-offs in speed, memory usage, and stability.
Comparison-Based Sorting
These algorithms sort elements by comparing pairs of elements against each other. Examples include Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, and Heap Sort. Comparison-based sorts have a theoretical lower bound of O(n log n) for the average/worst case.
Non-Comparison-Based Sorting
These algorithms sort without directly comparing elements, instead using properties of the data such as digit values or value ranges. Examples include Counting Sort, Radix Sort, and Bucket Sort. These can achieve O(n) time under the right conditions.
Comparison Table
| Algorithm | Best | Average | Worst | Stable | In-place |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Yes | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | No | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | Yes | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Yes | No |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | No | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | No | Yes |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | Yes | No |
| Radix Sort | O(nk) | O(nk) | O(nk) | Yes | No |
Choosing the Right Sort
- Use Insertion Sort for small or nearly sorted data.
- Use Merge Sort when stability and predictable O(n log n) performance are required.
- Use Quick Sort for general-purpose in-place sorting with good average performance.
- Use Counting/Radix Sort when data range or digit length is bounded and small.
Ready to master Data Structures & Algorithms?
Learn DSA hands-on with mentor-led sessions, real interview practice, and placement support.