Ugenz Academy/Tutorial

Sorting

14 min read2,630 words

Reading progress

Keep learning

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

AlgorithmBestAverageWorstSpace
BubbleO(n)O(n²)O(n²)O(1)
SelectionO(n²)O(n²)O(n²)O(1)
InsertionO(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:

  1. Build a max heap.
  2. Put the largest element at the end.
  3. Reduce heap size.
  4. Heapify.
  5. 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

AlgorithmBestAverageWorstSpaceStable
BubbleO(n)O(n²)O(n²)O(1)Yes
SelectionO(n²)O(n²)O(n²)O(1)No
InsertionO(n)O(n²)O(n²)O(1)Yes
MergeO(n log n)O(n log n)O(n log n)O(n)Yes
QuickO(n log n)O(n log n)O(n²)O(log n)*No
HeapO(n log n)O(n log n)O(n log n)O(1)No
CountingO(n+k)O(n+k)O(n+k)O(k)Can be
RadixO(d(n+k))O(d(n+k))O(d(n+k))DependsYes*

* 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

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy