Sorting in DSA
Sorting means arranging data in a particular order.
Usually:
Ascending: 1 2 3 4 5 6 Descending: 6 5 4 3 2 1
Sorting is one of the most important DSA topics because many algorithms become easier after data is sorted.
1. Why Do We Need Sorting?
Suppose we have:
45 12 89 23 7 34
Finding the smallest number is possible, but the data is not organized.
After sorting:
7 12 23 34 45 89
Now many operations become easier.
For example:
- Binary search
- Finding duplicates
- Finding median
- Finding minimum/maximum
- Merging data
- Interval problems
- Greedy algorithms
2. Types of Sorting
There are many sorting algorithms.
The most important ones for DSA are:
Sorting │ ├── Bubble Sort ├── Selection Sort ├── Insertion Sort ├── Merge Sort ├── Quick Sort ├── Heap Sort ├── Counting Sort ├── Radix Sort └── Bucket Sort
You should especially understand:
Bubble Selection Insertion Merge Quick Heap
3. Important Sorting Terms
Before learning algorithms, understand a few terms.
Ascending
1 2 3 4 5
Small → Large.
Descending
5 4 3 2 1
Large → Small.
Stable Sorting
A sorting algorithm is stable if equal elements maintain their original relative order.
Example:
(A, 90) (B, 80) (C, 90)
Sort by marks:
(B, 80) (A, 90) (C, 90)
A was before C, and remains before C.
4. Bubble Sort
Bubble Sort is one of the easiest sorting algorithms.
The idea:
Compare neighboring elements and swap them if they are in the wrong order.
Example:
5 3 8 4 2
Compare:
5 3
Since:
5 > 3
swap:
3 5 8 4 2
Next:
5 8
No swap.
Next:
8 4
Swap:
3 5 4 8 2
Next:
8 2
Swap:
3 5 4 2 8
After one complete pass:
3 5 4 2 8
The largest element 8 has "bubbled" to the end.
5. Bubble Sort Visualization
Initial: 5 3 8 4 2 ↓ compare 3 5 8 4 2 ↓ compare 3 5 8 4 2 ↓ compare 3 5 4 8 2 ↓ compare 3 5 4 2 8
Now 8 is in its correct position.
Repeat.
Eventually:
2 3 4 5 8
6. Bubble Sort Code
void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } }
Complexity:
Best: O(n) with optimization Average: O(n²) Worst: O(n²) Space: O(1)
Optimized version:
void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { bool swapped = false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); swapped = true; } } if (!swapped) break; } }
If the array is already sorted:
1 2 3 4 5
there are no swaps, so we can stop early.
7. Selection Sort
Selection Sort works differently.
The idea:
Find the smallest element and put it at the beginning.
Example:
64 25 12 22 11
Find minimum:
11
Swap with first element:
11 25 12 22 64
Now ignore the first position.
Remaining:
25 12 22 64
Minimum:
12
Swap:
11 12 25 22 64
Next minimum:
22
11 12 22 25 64
Finally:
11 12 22 25 64
8. Selection Sort Code
void selectionSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } swap(arr[i], arr[minIndex]); } }
Complexity:
Best: O(n²) Average: O(n²) Worst: O(n²) Space: O(1)
Unlike optimized Bubble Sort, Selection Sort still does roughly the same comparisons even if the array is already sorted.
9. Insertion Sort
Insertion Sort works similar to how we arrange cards in our hand.
Imagine:
5 2 4 6 1 3
Take 2.
5 | 2
Insert 2 before 5:
2 5
Take 4:
2 5 | 4
Insert it between 2 and 5:
2 4 5
Take 6:
2 4 5 6
Then 1:
1 2 4 5 6
Then 3:
1 2 3 4 5 6
10. Insertion Sort Code
void insertionSort(vector<int>& arr) { int n = arr.size(); for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }
Complexity:
Best: O(n) Average: O(n²) Worst: O(n²) Space: O(1)
Insertion Sort is particularly useful when:
- Data is nearly sorted.
- Input size is small.
- You need a simple in-place algorithm.
11. Bubble vs Selection vs Insertion
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) |
| Selection | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion | O(n) | O(n²) | O(n²) | O(1) |
These are mainly important for learning the fundamentals.
For large data, we generally prefer faster algorithms.
12. Merge Sort
Now we move to an important efficient algorithm.
Merge Sort uses:
Divide and Conquer
The idea:
Divide ↓ Sort smaller parts ↓ Merge them
Suppose:
8 3 5 4 7 6 1 2
Divide:
8 3 5 4 | 7 6 1 2
Again:
8 3 | 5 4 | 7 6 | 1 2
Again:
8 | 3 | 5 | 4 | 7 | 6 | 1 | 2
Now merge sorted pieces:
3 8 4 5 6 7 1 2
Then:
3 4 5 8 1 2 6 7
Finally:
1 2 3 4 5 6 7 8
13. Merge Sort Visualization
8 3 5 4 7 6 1 2 ↓ ┌─────────┴─────────┐ ↓ ↓ 8 3 5 4 7 6 1 2 ↓ ↓ 8 3 5 4 7 6 1 2 ↓ ↓ ↓ ↓ 8 3 4 5 6 7 1 2 ↓ ↓ 3 8 4 5 6 7 1 2 ↓ ↓ 3 4 5 8 1 2 6 7 ↓ 1 2 3 4 5 6 7 8
14. How Merge Works
Suppose we have two sorted arrays:
A = 2 5 8 B = 1 3 7
Compare first elements:
2 vs 1
Take 1.
1
Compare:
2 vs 3
Take 2.
1 2
Compare:
5 vs 3
Take 3.
Continue:
1 2 3 5 7 8
This merging operation takes:
O(n)
15. Merge Sort Code
void merge(vector<int>& arr, int left, int mid, int right) { vector<int> temp; int i = left; int j = mid + 1; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp.push_back(arr[i]); i++; } else { temp.push_back(arr[j]); j++; } } while (i <= mid) { temp.push_back(arr[i]); i++; } while (j <= right) { temp.push_back(arr[j]); j++; } for (int k = 0; k < temp.size(); k++) { arr[left + k] = temp[k]; } } void mergeSort(vector<int>& arr, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); }
Call:
mergeSort(arr, 0, arr.size() - 1);
Complexity:
Best: O(n log n) Average: O(n log n) Worst: O(n log n) Space: O(n)
Merge Sort is stable.
16. Why O(n log n)?
Each time we divide:
n n/2 n/4 n/8 ... 1
Number of levels:
log₂ n
At every level, merging takes:
O(n)
Therefore:
O(n) × O(log n)
=
O(n log n)
17. Quick Sort
Quick Sort is another major sorting algorithm.
It also uses:
Divide and Conquer
But instead of merging sorted arrays, Quick Sort chooses a:
Pivot
Then partitions the array around that pivot.
Example:
8 3 1 7 0 10 2
Suppose pivot:
7
Partition:
smaller than 7 | 7 | greater than 7
Approximately:
3 1 0 2 | 7 | 8 10
Then recursively sort the left and right parts.
18. Quick Sort Idea
[8 3 1 7 0 10 2] | pivot 7 | ┌──────────┴──────────┐ ↓ ↓ smaller greater 3 1 0 2 8 10 ↓ ↓ sort sort
19. Quick Sort Complexity
Average:
O(n log n)
Worst case:
O(n²)
The worst case can happen when the pivot selection is poor.
For example, already sorted data with a bad pivot strategy:
1 2 3 4 5 6 7
If we always choose the first element as pivot, the partitions can become extremely unbalanced.
With good pivot selection/randomization, Quick Sort performs very well in practice.
20. Heap Sort
You already learned Heap and Priority Queue, so Heap Sort connects directly to them.
For ascending order:
- Build a max heap.
- Put the largest element at the end.
- Reduce heap size.
- Heapify.
- Repeat.
Example:
5 3 8 4 1
Build max heap:
8 4 5 3 1
Move largest to the end:
5 4 1 3 | 8
Continue:
4 3 1 5 8
Then:
3 1 4 5 8
Finally:
1 3 4 5 8
Complexity:
Best: O(n log n) Average: O(n log n) Worst: O(n log n) Space: O(1)
Heap Sort is not stable.
21. Counting Sort
Counting Sort is different from comparison-based sorting.
Suppose:
4 2 2 8 3 3 1
Find frequency:
Number Frequency 1 1 2 2 3 2 4 1 5 0 6 0 7 0 8 1
Then reconstruct:
1 2 2 3 3 4 8
Complexity is approximately:
O(n + k)
where:
n = number of elements k = range of values
Counting Sort is useful when the value range is reasonably small.
22. Radix Sort
Radix Sort sorts numbers digit by digit.
Example:
170 045 075 090 802 024 002 066
It processes:
ones digit ↓ tens digit ↓ hundreds digit
It commonly uses a stable sorting method such as Counting Sort internally.
For suitable integer ranges, its complexity can be approximately:
O(d × (n + k))
where d is the number of digits.
23. Bucket Sort
Bucket Sort distributes elements into different buckets.
Example:
0.12 0.25 0.37 0.42 0.68 0.91
Conceptually:
Bucket 0 → 0.12 0.25 Bucket 1 → 0.37 0.42 Bucket 2 → 0.68 Bucket 3 → 0.91
Sort each bucket and combine them.
Its performance depends heavily on how the data is distributed.
24. Comparison-Based vs Non-Comparison Sorting
Comparison-based
Elements are compared:
a < b
Examples:
Bubble Selection Insertion Merge Quick Heap
For general comparison sorting, the theoretical lower bound is:
Ω(n log n)
for the worst-case comparison model.
Non-comparison
They use properties of the values rather than directly comparing every pair.
Examples:
Counting Sort Radix Sort Bucket Sort
These can beat O(n log n) under suitable assumptions about the input.
25. C++ STL Sorting
In real C++ programming, you will frequently use:
sort(arr.begin(), arr.end());
Example:
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> arr = {5, 2, 8, 1, 3}; sort(arr.begin(), arr.end()); for (int x : arr) { cout << x << " "; } return 0; }
Output:
1 2 3 5 8
26. Descending Order
Use:
sort(arr.begin(), arr.end(), greater<int>());
Example:
8 5 3 2 1
27. Sorting Strings
vector<string> names = { "Uday", "Aman", "Rahul", "Bikash" }; sort(names.begin(), names.end());
Result:
Aman Bikash Rahul Uday
28. Custom Sorting
Suppose:
vector<pair<string, int>> students = { {"Uday", 85}, {"Aman", 95}, {"Rahul", 75} };
Sort by marks:
sort(students.begin(), students.end(), [](auto& a, auto& b) { return a.second > b.second; });
Result:
Aman 95 Uday 85 Rahul 75
Custom comparators become very important in competitive programming and interviews.
29. Important Sorting Comparison
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n)* | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting | O(n+k) | O(n+k) | O(n+k) | O(k) | Can be |
| Radix | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | Depends | Yes* |
* depends on implementation/details.
30. Which Sorting Algorithm Should You Remember?
For DSA, remember the progression:
Simple ↓ Bubble Selection Insertion ↓ Efficient ↓ Merge Quick Heap ↓ Special cases ↓ Counting Radix Bucket
The most important concepts are:
Bubble Sort → Adjacent swapping Selection Sort → Select minimum/maximum Insertion Sort → Insert into sorted portion Merge Sort → Divide + Merge Quick Sort → Pivot + Partition Heap Sort → Heap
31. Sorting and Other DSA Topics
Sorting connects with many topics you have already learned:
Arrays ↓ Sorting ↓ Binary Search ↓ Greedy Algorithms ↓ Divide & Conquer ↓ Dynamic Programming
For example:
Merge Sort → Divide and Conquer
Heap Sort → Heap
Quick Sort → Divide and Conquer
Sorting → Searching
Priority Queue → Heap
So sorting is a major bridge between the basic and advanced parts of DSA.
Final Summary
SORTING │ ├── Bubble Sort │ └── Compare adjacent elements │ ├── Selection Sort │ └── Select minimum/maximum │ ├── Insertion Sort │ └── Insert into sorted section │ ├── Merge Sort │ └── Divide + Merge │ ├── Quick Sort │ └── Pivot + Partition │ ├── Heap Sort │ └── Heap │ ├── Counting Sort │ └── Frequency │ ├── Radix Sort │ └── Digit by digit │ └── Bucket Sort └── Distribute into buckets
The most important complexity to remember:
O(n²) → Bubble → Selection → Insertion O(n log n) → Merge → Heap → Quick (average) O(n + k) → Counting