Sorting Algorithms: Explanation, C++ Code, and

Comparison

Prepared for Interview Preparation

August 15, 2025

1 Introduction
This document explains eight common sorting algorithms: Bubble Sort, Selection Sort,
Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Radix Sort, and Counting Sort. Each
algorithm is demonstrated with the example array [5, 2, 4, 6, 1, 3], followed by its C++
implementation, a comparison table, and interview-relevant notes.

2 Example Array
All algorithms are demonstrated with the array: [5, 2, 4, 6, 1, 3].

3 Bubble Sort
3.1 Description
Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps
them if they are in the wrong order. The process continues until no swaps are needed.

3.2 Example
• Initial: [5, 2, 4, 6, 1, 3]
• Pass 1: Compare 5, 2 (swap: [2, 5, 4, 6, 1, 3]), 5, 4 (swap: [2, 4, 5, 6, 1, 3]), 5, 6 (no
swap), 6, 1 (swap: [2, 4, 5, 1, 6, 3]), 6, 3 (swap: [2, 4, 5, 1, 3, 6])
• Pass 2: [2, 4, 1, 5, 3, 6] (swap 4, 1), [2, 1, 4, 5, 3, 6] (swap 2, 1), [1, 2, 4, 5, 3, 6] (no more
swaps in this pass)
• Pass 3: [1, 2, 4, 3, 5, 6] (swap 5, 3)
• Pass 4: [1, 2, 3, 4, 5, 6] (swap 4, 3)
• Pass 5: No swaps, array is sorted.
Final: [1, 2, 3, 4, 5, 6]

1
 3.3 C++ Code
1 # include <iostream >
2 void swap(int& a, int& b) {
3 int temp = a;
4 a = b;
5 b = temp;
6 }
7 void bubbleSort (int arr [], int n) {
8 for (int i = 0; i < n - 1; i++) {
9 bool swapped = false ;
10 for (int j = 0; j < n - i - 1; j++) {
11 if (arr[j] > arr[j + 1]) {
12 swap(arr[j], arr[j + 1]);
13 swapped = true;
14 }
15 }
16 if (! swapped ) break ;
17 }
18 }
19 int main () {
20 int arr [] = {5, 2, 4, 6, 1, 3};
21 int n = sizeof (arr) / sizeof (arr [0]);
22 bubbleSort (arr , n);
23 for (int i = 0; i < n; i++) std :: cout << arr[i] << " ";
24 return 0;
25 }

4 Selection Sort
4.1 Description
Selection Sort divides the array into sorted and unsorted parts. In each iteration, it finds
the minimum element in the unsorted part and places it at the beginning of the unsorted
part.

4.2 Example
• Initial: [5, 2, 4, 6, 1, 3]
• Iteration 1: Min = 1 (index 4), swap with 5: [1, 2, 4, 6, 5, 3]
• Iteration 2: Min = 2 (index 1), no swap: [1, 2, 4, 6, 5, 3]
• Iteration 3: Min = 3 (index 5), swap with 4: [1, 2, 3, 6, 5, 4]
• Iteration 4: Min = 4 (index 5), swap with 6: [1, 2, 3, 4, 5, 6]
• Iteration 5: Min = 5, no swap (already in place).
Final: [1, 2, 3, 4, 5, 6]

2
 4.3 C++ Code
1 # include <iostream >
2 void selectionSort (int arr [], int n) {
3 for (int i = 0; i < n - 1; i++) {
4 int min_idx = i;
5 for (int j = i + 1; j < n; j++)
6 if (arr[j] < arr[ min_idx ])
7 min_idx = j;
8 if ( min_idx != i) {
9 int temp = arr[i];
10 arr[i] = arr[ min_idx ];
11 arr[ min_idx ] = temp;
12 }
13 }
14 }
15 int main () {
16 int arr [] = {5, 2, 4, 6, 1, 3};
17 int n = sizeof (arr) / sizeof (arr [0]);
18 selectionSort (arr , n);
19 for (int i = 0; i < n; i++) std :: cout << arr[i] << " ";
20 return 0;
21 }

5 Insertion Sort
5.1 Description
Insertion Sort builds the sorted array one element at a time by taking an element from
the unsorted part and inserting it into the correct position in the sorted part.

5.2 Example
• Initial: [5, 2, 4, 6, 1, 3]
• Step 1: [5, 2, 4, 6, 1, 3] (5 is sorted)
• Step 2: Insert 2 before 5: [2, 5, 4, 6, 1, 3]
• Step 3: Insert 4 between 2, 5: [2, 4, 5, 6, 1, 3]
• Step 4: 6 stays in place: [2, 4, 5, 6, 1, 3]
• Step 5: Insert 1 at start: [1, 2, 4, 5, 6, 3]
• Step 6: Insert 3 between 2, 4: [1, 2, 3, 4, 5, 6]
Final: [1, 2, 3, 4, 5, 6]

5.3 C++ Code

1 # include <iostream >
2 void insertionSort (int arr [], int n) {

3
3 for (int i = 1; i < n; i++) {
4 int key = arr[i];
5 int j = i - 1;
6 while (j >= 0 && arr[j] > key) {
7 arr[j + 1] = arr[j];
8 j--;
9 }
10 arr[j + 1] = key;
11 }
12 }
13 int main () {
14 int arr [] = {5, 2, 4, 6, 1, 3};
15 int n = sizeof (arr) / sizeof (arr [0]);
16 insertionSort (arr , n);
17 for (int i = 0; i < n; i++) std :: cout << arr[i] << " ";
18 return 0;
19 }

6 Merge Sort
6.1 Description
Merge Sort divides the array into two halves, recursively sorts them, and then merges
the sorted halves to produce a sorted array.

6.2 Example
• Initial: [5, 2, 4, 6, 1, 3]
• Divide: [5, 2, 4] and [6, 1, 3]
• Divide: [5, 2], [4] and [6, 1], [3]
• Divide: [5], [2] and [6], [1]
• Merge: [2, 5], [4], [1, 6], [3]
• Merge: [2, 4, 5], [1, 3, 6]
• Merge: [1, 2, 3, 4, 5, 6]
Final: [1, 2, 3, 4, 5, 6]

6.3 C++ Code

1 # include <iostream >
2 void merge(int arr [], int l, int m, int r) {
3 int n1 = m - l + 1, n2 = r - m;
4 int L[n1], R[n2];
5 for (int i = 0; i < n1; i++) L[i] = arr[l + i];
6 for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];
7 int i = 0, j = 0, k = l;

4
8 while (i < n1 && j < n2) {
9 if (L[i] <= R[j]) arr[k++] = L[i++];
10 else arr[k++] = R[j++];
11 }
12 while (i < n1) arr[k++] = L[i++];
13 while (j < n2) arr[k++] = R[j++];
14 }
15 void mergeSort (int arr [], int l, int r) {
16 if (l < r) {
17 int m = l + (r - l) / 2;
18 mergeSort (arr , l, m);
19 mergeSort (arr , m + 1, r);
20 merge(arr , l, m, r);
21 }
22 }
23 int main () {
24 int arr [] = {5, 2, 4, 6, 1, 3};
25 int n = sizeof (arr) / sizeof (arr [0]);
26 mergeSort (arr , 0, n - 1);
27 for (int i = 0; i < n; i++) std :: cout << arr[i] << " ";
28 return 0;
29 }

7 Quick Sort
7.1 Description
Quick Sort selects a pivot (here, the last element), partitions the array so that elements
less than the pivot are on the left and greater on the right, and recursively sorts the
sub-arrays.

7.2 Example
• Initial: [5, 2, 4, 6, 1, 3], pivot = 3
• Partition: [2, 1, 3, 6, 5, 4] (elements ≤ 3 on left, > 3 on right)
• Left: [2, 1], pivot = 1: [1, 2]
• Right: [6, 5, 4], pivot = 4: [4, 5, 6]
• Final: [1, 2, 3, 4, 5, 6]

7.3 C++ Code

1 # include <iostream >
2 void swap(int& a, int& b) {
3 int temp = a;
4 a = b;
5 b = temp;
6 }

5
7 int partition (int arr [], int low , int high) {
8 int pivot = arr[high ];
9 int i = low - 1;
10 for (int j = low; j <= high - 1; j++) {
11 if (arr[j] <= pivot ) {
12 i++;
13 swap(arr[i], arr[j]);
14 }
15 }
16 swap(arr[i + 1], arr[high ]);
17 return i + 1;
18 }
19 void quickSort (int arr [], int low , int high) {
20 if (low < high) {
21 int pi = partition (arr , low , high);
22 quickSort (arr , low , pi - 1);
23 quickSort (arr , pi + 1, high);
24 }
25 }
26 int main () {
27 int arr [] = {5, 2, 4, 6, 1, 3};
28 int n = sizeof (arr) / sizeof (arr [0]);
29 quickSort (arr , 0, n - 1);
30 for (int i = 0; i < n; i++) std :: cout << arr[i] << " ";
31 return 0;
32 }

8 Heap Sort
8.1 Description
Heap Sort builds a max-heap from the array, repeatedly extracts the maximum element,
and places it at the end, reducing the heap size each time.

8.2 Example
• Initial: [5, 2, 4, 6, 1, 3]
• Build Max-Heap: [6, 2, 5, 1, 4, 3]
• Extract Max: [5, 2, 3, 1, 4, 6], heapify: [5, 2, 3, 1, 4]
• Extract Max: [4, 2, 3, 1, 5, 6], heapify: [4, 2, 3, 1]
• Continue: [3, 2, 1, 4, 5, 6], [2, 1, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]
Final: [1, 2, 3, 4, 5, 6]

8.3 C++ Code

1 # include <iostream >

6
2 void heapify (int arr [], int n, int i) {
3 int largest = i, left = 2 * i + 1, right = 2 * i + 2;
4 if (left < n && arr[left] > arr[ largest ]) largest = left;
5 if (right < n && arr[ right ] > arr[ largest ]) largest = right ;
6 if ( largest != i) {
7 int temp = arr[i];
8 arr[i] = arr[ largest ];
9 arr[ largest ] = temp;
10 heapify (arr , n, largest );
11 }
12 }
13 void heapSort (int arr [], int n) {
14 for (int i = n / 2 - 1; i >= 0; i--) heapify (arr , n, i);
15 for (int i = n - 1; i > 0; i--) {
16 int temp = arr [0];
17 arr [0] = arr[i];
18 arr[i] = temp;
19 heapify (arr , i, 0);
20 }
21 }
22 int main () {
23 int arr [] = {5, 2, 4, 6, 1, 3};
24 int n = sizeof (arr) / sizeof (arr [0]);
25 heapSort (arr , n);
26 for (int i = 0; i < n; i++) std :: cout << arr[i] << " ";
27 return 0;
28 }

9 Radix Sort
9.1 Description
Radix Sort sorts integers by processing individual digits (from least to most significant)
using a stable counting sort for each digit.

9.2 Example
• Initial: [5, 2, 4, 6, 1, 3]
• Digit 1 (units): [1, 2, 3, 4, 5, 6]
• No further digits needed (single-digit numbers).
Final: [1, 2, 3, 4, 5, 6]

9.3 C++ Code

1 # include <iostream >
2 int getMax (int arr [], int n) {
3 int max = arr [0];
4 for (int i = 1; i < n; i++) if (arr[i] > max) max = arr[i];

7
5 return max;
6 }
7 void countingSort (int arr [], int n, int exp) {
8 int output [n], count [10] = {0};
9 for (int i = 0; i < n; i++) count [( arr[i] / exp) % 10]++;
10 for (int i = 1; i < 10; i++) count [i] += count [i - 1];
11 for (int i = n - 1; i >= 0; i--) {
12 output [count [( arr[i] / exp) % 10] - 1] = arr[i];
13 count [( arr[i] / exp) % 10] - -;
14 }
15 for (int i = 0; i < n; i++) arr[i] = output [i];
16 }
17 void radixSort (int arr [], int n) {
18 int max = getMax (arr , n);
19 for (int exp = 1; max / exp > 0; exp *= 10)
20 countingSort (arr , n, exp);
21 }
22 int main () {
23 int arr [] = {5, 2, 4, 6, 1, 3};
24 int n = sizeof (arr) / sizeof (arr [0]);
25 radixSort (arr , n);
26 for (int i = 0; i < n; i++) std :: cout << arr[i] << " ";
27 return 0;
28 }

10 Counting Sort
10.1 Description
Counting Sort counts the occurrences of each value in the array and uses this to place
elements in their correct positions. It assumes integers within a specific range.

10.2 Example
• Initial: [5, 2, 4, 6, 1, 3], range = 1 to 6
• Count: [1, 1, 1, 1, 1, 1] (one occurrence each)
• Cumulative Count: [1, 2, 3, 4, 5, 6]
• Place elements: [1, 2, 3, 4, 5, 6]
Final: [1, 2, 3, 4, 5, 6]

10.3 C++ Code

1 # include <iostream >
2 void countingSort (int arr [], int n, int max) {
3 int count[max + 1] = {0} , output [n];
4 for (int i = 0; i < n; i++) count [arr[i ]]++;
5 for (int i = 1; i <= max; i++) count[i] += count [i - 1];

8
6 for (int i = n - 1; i >= 0; i--) {
7 output [count [arr[i]] - 1] = arr[i];
8 count[arr[i]]--;
9 }
10 for (int i = 0; i < n; i++) arr[i] = output [i];
11 }
12 int main () {
13 int arr [] = {5, 2, 4, 6, 1, 3};
14 int n = sizeof (arr) / sizeof (arr [0]);
15 int max = 6; // Known max value
16 countingSort (arr , n, max);
17 for (int i = 0; i < n; i++) std :: cout << arr[i] << " ";
18 return 0;
19 }

11 Comparison Table

Table 1: Comparison of Sorting Algorithms

Algorithm Best Average Worst Space Stable In-Place
Bubble Sort O(n) O(n2 ) O(n2 ) O(1) Yes Yes
2 2 2
Selection Sort O(n ) O(n ) O(n ) O(1) No Yes
2 2
Insertion Sort O(n) O(n ) O(n ) O(1) Yes Yes
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes No
2
Quick Sort O(n log n) O(n log n) O(n ) O(log n) No Yes
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No Yes
Radix Sort O(nk) O(nk) O(nk) O(n + k) Yes No
Counting Sort O(n + k) O(n + k) O(n + k) O(k) Yes No

12 Interview Notes
• Bubble Sort: Simple, good for small datasets or teaching. Rarely used in practice
due to inefficiency.
• Selection Sort: Easy to implement, performs well on small lists, but poor for
large datasets. Not stable.
• Insertion Sort: Efficient for small or nearly sorted arrays, adaptive, stable. Used
in hybrid algorithms like TimSort.
• Merge Sort: Stable, predictable O(n log n), good for linked lists or large datasets.
Requires extra space.
• Quick Sort: Fast in practice, in-place, but worst-case O(n2 ) with poor pivot
choices. Not stable.
• Heap Sort: In-place, O(n log n), but slower than Quick Sort in practice due to
poor cache performance. Not stable.

9
• Radix Sort: Efficient for integers or strings with fixed-length keys. Requires
multiple passes based on digit count.
• Counting Sort: Best for small integer ranges. Fast and stable but requires extra
space proportional to range.
• Interview Tips: Be ready to discuss pivot selection in Quick Sort, heap construc-
tion in Heap Sort, and stability’s impact. Know when to use non-comparison sorts
(Radix, Counting) for integers. Explain trade-offs (e.g., space vs. time, stability
vs. in-place).

10