Sorting is a fundamental concept in computer science. It helps us organize data so we can search it more efficiently, visualize it better, or process it faster. In this blog, we’ll cover elementary sorts (Selection, Insertion, Shell) and efficient sorts (Merge Sort, Quicksort, 3-Way Quicksort). We’ll explain each with simple code and then provide a comparison table at the end.
1. Selection Sort
How it works:
- Repeatedly finds the minimum element from the unsorted part of the array and swaps it to the front.
Code:
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[minIdx])
minIdx = j;
swap(arr[i], arr[minIdx]);
}
}
Key Points:
- Easy to understand
- Inefficient on large arrays
- Not stable
2. Insertion Sort
How it works:
- Builds the sorted array one element at a time by inserting each element into its correct position.
Code:
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
Key Points:
- Great for small or nearly sorted arrays
- Stable
- Performs well on small data sets
3. Shell Sort
How it works:
- Improves insertion sort by allowing comparisons and exchanges far apart. It uses a gap sequence that reduces over time.
Code:
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i], j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
}
Key Points:
- Much faster than selection/insertion for medium-sized data
- Not stable
- Gap sequences affect performance
To have a more robust understanding of these 3 elementary sorts, you may like to explore Elementary Sorting Algorithms in C++ (Selection, Insertion, Shell Sort)
4. Top-Down Merge Sort
How it works:
- Recursively splits the array into halves, sorts them, and merges them back.
Code:
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2)
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
Key Points:
- Stable
- Excellent performance
- Requires extra space for merging
5. Bottom-Up Merge Sort
How it works:
- An iterative version of merge sort that starts by merging pairs of single elements, then doubles the size each time.
Code:
void bottomUpMergeSort(int arr[], int n) {
for (int size = 1; size < n; size *= 2) {
for (int left = 0; left < n - size; left += 2 * size) {
int mid = left + size - 1;
int right = min(left + 2 * size - 1, n - 1);
merge(arr, left, mid, right);
}
}
}
Key Points:
- Avoids recursion
- Good for linked list implementations
- Same performance as top-down
To have a more understanding of these 2 types of merge sorts, you may like to explore: Merge Sort in C++: Top-Down and Bottom-Up Approaches
6. Quicksort
How it works:
- Picks a pivot, partitions the array such that elements < pivot are on the left and > pivot on the right, and recursively sorts both parts.
Code:
int partition(int arr[], int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot)
swap(arr[++i], arr[j]);
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int p = partition(arr, low, high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}
}
Key Points:
- Fastest in practice
- Not stable
- Worst case: O(n²) but average is O(n log n)
7. 3-Way Quicksort
How it works:
- Partitions the array into three parts:
- Elements less than the pivot
- Elements equal to the pivot
- Elements greater than the pivot
Code:
void quickSort3Way(int arr[], int low, int high) {
if (low >= high) return;
int lt = low, i = low + 1, gt = high;
int pivot = arr[low];
while (i <= gt) {
if (arr[i] < pivot) swap(arr[i++], arr[lt++]);
else if (arr[i] > pivot) swap(arr[i], arr[gt--]);
else i++;
}
quickSort3Way(arr, low, lt - 1);
quickSort3Way(arr, gt + 1, high);
}
Key Points:
- Extremely efficient when many duplicates are present
- Not stable
- Slightly more complex than standard quicksort
To have a more robust understanding of these QuickSort programs, you may like to explore: Quick Sort in C++ — Full Guide for Beginners
Comparison Table
| Algorithm | Time Complexity (Avg) | Time (Worst) | Space | Stable | In-Place | Suitable For |
|---|---|---|---|---|---|---|
| Selection Sort | O(n²) | O(n²) | O(1) | No | Yes | Simple intro to sorting |
| Insertion Sort | O(n²) | O(n²) | O(1) | Yes | Yes | Small or nearly sorted arrays |
| Shell Sort | O(n log n) approx. | O(n²) | O(1) | No | Yes | Medium arrays |
| Merge Sort (TD) | O(n log n) | O(n log n) | O(n) | Yes | No | Large arrays; stability needed |
| Merge Sort (BU) | O(n log n) | O(n log n) | O(n) | Yes | No | Iterative needs, linked lists |
| Quicksort | O(n log n) | O(n²) | O(log n) | No | Yes | Fastest general-purpose sorter |
| 3-Way Quicksort | O(n log n) | O(n²) | O(log n) | No | Yes | Arrays with many duplicates |