Sorting is one of the most fundamental operations in computer science, forming the backbone of countless applications from database indexing to search optimization. Understanding sorting algorithms not only helps you write better code but also builds intuition for algorithm design, complexity analysis, and optimization techniques. This comprehensive guide explores the most important sorting algorithms implemented in C, from simple quadratic sorts to advanced O(n log n) algorithms.

Why Sorting Matters

Sorting is essential because:

• Search Optimization: Binary search requires sorted data
• Data Analysis: Sorted data reveals patterns and statistics
• Database Indexing: B-trees and other indexes rely on ordering
• Algorithm Foundation: Many algorithms assume sorted input
• User Experience: Users expect sorted output

Complexity Classes

Class	Time Complexity	Algorithms
Quadratic	O(n²)	Bubble Sort, Selection Sort, Insertion Sort
Linearithmic	O(n log n)	Merge Sort, Quick Sort, Heap Sort
Linear	O(n)	Counting Sort, Radix Sort, Bucket Sort (with assumptions)
Adaptive	O(n) to O(n²)	Insertion Sort, Timsort

---

Part 1: Quadratic Sorts (O(n²))

1. Bubble Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order.

#include <stdio.h>
#include <stdbool.h>
// Basic Bubble Sort
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Optimized Bubble Sort with early termination
void bubble_sort_optimized(int arr[], int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no swaps, array is sorted
if (!swapped) break;
}
}
// Bidirectional Bubble Sort (Cocktail Shaker Sort)
void cocktail_sort(int arr[], int n) {
bool swapped = true;
int start = 0;
int end = n - 1;
while (swapped) {
swapped = false;
// Forward pass
for (int i = start; i < end; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
end--;
swapped = false;
// Backward pass
for (int i = end - 1; i >= start; i--) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
start++;
}
}

Time Complexity: O(n²) average/worst, O(n) best (optimized)
Space Complexity: O(1)
Stable: Yes
When to use: Educational purposes, nearly sorted data

---

2. Selection Sort

Selection Sort divides the array into sorted and unsorted portions, repeatedly selecting the minimum from the unsorted portion.

// Basic Selection Sort
void selection_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
// Find minimum element in unsorted portion
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// Swap if needed
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}
// Selection Sort for double array (generic version)
void selection_sort_generic(void *arr, size_t n, size_t size,
int (*cmp)(const void *, const void *)) {
char *base = (char *)arr;
for (size_t i = 0; i < n - 1; i++) {
size_t min_idx = i;
for (size_t j = i + 1; j < n; j++) {
if (cmp(base + j * size, base + min_idx * size) < 0) {
min_idx = j;
}
}
if (min_idx != i) {
// Swap elements
char temp[size];
memcpy(temp, base + i * size, size);
memcpy(base + i * size, base + min_idx * size, size);
memcpy(base + min_idx * size, temp, size);
}
}
}
// Comparison function for integers
int cmp_int(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}

Time Complexity: O(n²) all cases
Space Complexity: O(1)
Stable: No
When to use: When memory writes are expensive (minimal swaps)

---

3. Insertion Sort

Insertion Sort builds the final sorted array one element at a time, inserting each element into its correct position.

// Basic Insertion Sort
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Shift elements greater than key
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// Binary Insertion Sort (using binary search for insertion point)
void binary_insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
// Binary search for insertion point
int left = 0, right = i - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Shift elements
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = key;
}
}
// Shell Sort (generalization of insertion sort)
void shell_sort(int arr[], int n) {
// Start with a large gap, then reduce
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
// Shell Sort with Knuth's sequence
void shell_sort_knuth(int arr[], int n) {
// Generate Knuth sequence: 1, 4, 13, 40, 121, ...
int gap = 1;
while (gap < n / 3) {
gap = gap * 3 + 1;
}
while (gap >= 1) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
gap /= 3;
}
}

Time Complexity: O(n²) worst, O(n) best, O(n^(3/2)) for Shell Sort
Space Complexity: O(1)
Stable: Yes
When to use: Small arrays, nearly sorted data, online sorting

---

Part 2: Divide and Conquer Sorts (O(n log n))

4. Merge Sort

Merge Sort divides the array into halves, recursively sorts them, then merges the sorted halves.

#include <stdlib.h>
#include <string.h>
// Merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
int *L = (int *)malloc(n1 * sizeof(int));
int *R = (int *)malloc(n2 * sizeof(int));
// Copy data
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge back
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
// Copy remaining elements
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
free(L);
free(R);
}
// Recursive merge sort
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
// Bottom-up Merge Sort (iterative)
void merge_sort_bottom_up(int arr[], int n) {
// Allocate temporary array once
int *temp = (int *)malloc(n * sizeof(int));
for (int width = 1; width < n; width *= 2) {
for (int i = 0; i < n; i += 2 * width) {
int left = i;
int mid = (i + width - 1 < n - 1) ? i + width - 1 : n - 1;
int right = (i + 2 * width - 1 < n - 1) ? i + 2 * width - 1 : n - 1;
if (mid < right) {
// Merge into temporary array
int l = left, r = mid + 1, k = left;
while (l <= mid && r <= right) {
if (arr[l] <= arr[r]) {
temp[k++] = arr[l++];
} else {
temp[k++] = arr[r++];
}
}
while (l <= mid) temp[k++] = arr[l++];
while (r <= right) temp[k++] = arr[r++];
// Copy back
for (k = left; k <= right; k++) {
arr[k] = temp[k];
}
}
}
}
free(temp);
}
// In-place merge sort (less memory, more complex)
void merge_in_place(int arr[], int left, int mid, int right) {
// Implementation using rotation technique
int i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
i++;
} else {
int value = arr[j];
int idx = j;
// Shift elements
while (idx > i) {
arr[idx] = arr[idx - 1];
idx--;
}
arr[i] = value;
i++;
mid++;
j++;
}
}
}
// Natural merge sort (uses existing runs)
void natural_merge_sort(int arr[], int n) {
int *temp = (int *)malloc(n * sizeof(int));
while (1) {
int run_start = 0;
int runs = 0;
// Find runs
while (run_start < n) {
// Find end of run
int run_end = run_start;
while (run_end + 1 < n && arr[run_end] <= arr[run_end + 1]) {
run_end++;
}
// If this was the only run, we're done
if (run_end == n - 1 && runs == 0) {
free(temp);
return;
}
// Find next run
int next_start = run_end + 1;
if (next_start >= n) break;
int next_end = next_start;
while (next_end + 1 < n && arr[next_end] <= arr[next_end + 1]) {
next_end++;
}
// Merge runs
int i = run_start, j = next_start, k = run_start;
while (i <= run_end && j <= next_end) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= run_end) temp[k++] = arr[i++];
while (j <= next_end) temp[k++] = arr[j++];
// Copy back
for (i = run_start; i <= next_end; i++) {
arr[i] = temp[i];
}
run_start = next_end + 1;
runs++;
}
}
}

Time Complexity: O(n log n) all cases
Space Complexity: O(n)
Stable: Yes
When to use: Large datasets, linked lists, external sorting

---

5. Quick Sort

Quick Sort selects a pivot, partitions the array around it, and recursively sorts the partitions.

#include <stdlib.h>
// Partition function
int partition(int arr[], int low, int high) {
int pivot = arr[high];  // Choose last element as pivot
int i = low - 1;        // Index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
// Swap
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Place pivot in correct position
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// Partition with median-of-three pivot selection
int median_of_three(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
// Sort low, mid, high
if (arr[low] > arr[mid]) {
int temp = arr[low];
arr[low] = arr[mid];
arr[mid] = temp;
}
if (arr[low] > arr[high]) {
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
if (arr[mid] > arr[high]) {
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
}
// Place median at high-1
int temp = arr[mid];
arr[mid] = arr[high - 1];
arr[high - 1] = temp;
return arr[high - 1];
}
int partition_median(int arr[], int low, int high) {
if (high - low > 2) {
median_of_three(arr, low, high);
// Use arr[high-1] as pivot
int pivot = arr[high - 1];
int i = low - 1;
for (int j = low; j < high - 1; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high - 1];
arr[high - 1] = temp;
return i + 1;
}
return partition(arr, low, high);
}
// Recursive quick sort
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
// Quick Sort with insertion sort for small subarrays
void quick_sort_hybrid(int arr[], int low, int high) {
const int THRESHOLD = 10;
if (high - low <= THRESHOLD) {
// Use insertion sort for small subarrays
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
} else {
int pi = partition_median(arr, low, high);
quick_sort_hybrid(arr, low, pi - 1);
quick_sort_hybrid(arr, pi + 1, high);
}
}
// 3-way Quick Sort (handles duplicates efficiently)
void quick_sort_3way(int arr[], int low, int high) {
if (low >= high) return;
int pivot = arr[low];
int lt = low;      // Less than pivot
int gt = high;     // Greater than pivot
int i = low + 1;
while (i <= gt) {
if (arr[i] < pivot) {
int temp = arr[lt];
arr[lt] = arr[i];
arr[i] = temp;
lt++;
i++;
} else if (arr[i] > pivot) {
int temp = arr[gt];
arr[gt] = arr[i];
arr[i] = temp;
gt--;
} else {
i++;
}
}
quick_sort_3way(arr, low, lt - 1);
quick_sort_3way(arr, gt + 1, high);
}
// Iterative Quick Sort using explicit stack
void quick_sort_iterative(int arr[], int n) {
int *stack = (int *)malloc(2 * n * sizeof(int));
int top = -1;
stack[++top] = 0;
stack[++top] = n - 1;
while (top >= 0) {
int high = stack[top--];
int low = stack[top--];
int pi = partition(arr, low, high);
if (pi - 1 > low) {
stack[++top] = low;
stack[++top] = pi - 1;
}
if (pi + 1 < high) {
stack[++top] = pi + 1;
stack[++top] = high;
}
}
free(stack);
}

Time Complexity: O(n log n) average, O(n²) worst
Space Complexity: O(log n)
Stable: No
When to use: General-purpose sorting, large datasets

---

6. Heap Sort

Heap Sort builds a max-heap and repeatedly extracts the maximum element.

#include <stdlib.h>
// Heapify a subtree rooted at index i
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
// Build max heap
void build_heap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
}
// Heap Sort
void heap_sort(int arr[], int n) {
build_heap(arr, n);
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify reduced heap
heapify(arr, i, 0);
}
}
// Iterative heapify (no recursion)
void heapify_iterative(int arr[], int n, int i) {
while (1) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest == i) break;
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
i = largest;
}
}

Time Complexity: O(n log n) all cases
Space Complexity: O(1)
Stable: No
When to use: When guaranteed O(n log n) is needed, memory constrained

---

Part 3: Linear Sorts (O(n))

7. Counting Sort

Counting Sort assumes integer keys in a known range.

#include <stdlib.h>
#include <string.h>
void counting_sort(int arr[], int n) {
if (n <= 1) return;
// Find range
int max = arr[0], min = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
int range = max - min + 1;
// Count array
int *count = (int *)calloc(range, sizeof(int));
// Store count of each element
for (int i = 0; i < n; i++) {
count[arr[i] - min]++;
}
// Modify count to store cumulative positions
for (int i = 1; i < range; i++) {
count[i] += count[i - 1];
}
// Build output array
int *output = (int *)malloc(n * sizeof(int));
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
// Copy back
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
free(count);
free(output);
}
// Counting Sort for unsigned integers (faster)
void counting_sort_unsigned(unsigned int arr[], size_t n) {
if (n <= 1) return;
unsigned int max = arr[0];
for (size_t i = 1; i < n; i++) {
if (arr[i] > max) max = arr[i];
}
unsigned int *count = (unsigned int *)calloc(max + 1, sizeof(unsigned int));
for (size_t i = 0; i < n; i++) {
count[arr[i]]++;
}
size_t index = 0;
for (unsigned int i = 0; i <= max; i++) {
while (count[i]--) {
arr[index++] = i;
}
}
free(count);
}

Time Complexity: O(n + k) where k is range
Space Complexity: O(k)
Stable: Yes
When to use: Small integer ranges

---

8. Radix Sort

Radix Sort processes digits from least significant to most significant.

// Get maximum value
int get_max(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
// Counting sort by digit
void counting_sort_by_digit(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
// Count occurrences
for (int i = 0; i < n; i++) {
int digit = (arr[i] / exp) % 10;
count[digit]++;
}
// Cumulative count
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build output array
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
// Copy back
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// LSD Radix Sort
void radix_sort_lsd(int arr[], int n) {
int max = get_max(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10) {
counting_sort_by_digit(arr, n, exp);
}
}
// MSD Radix Sort (most significant digit first)
void radix_sort_msd_recursive(int arr[], int left, int right, int exp) {
if (left >= right || exp <= 0) return;
int buckets[10];
int *temp = (int *)malloc((right - left + 1) * sizeof(int));
// Initialize buckets
for (int i = 0; i < 10; i++) buckets[i] = 0;
// Count elements in each bucket
for (int i = left; i <= right; i++) {
int digit = (arr[i] / exp) % 10;
buckets[digit]++;
}
// Calculate cumulative positions
int cumsum[10];
cumsum[0] = 0;
for (int i = 1; i < 10; i++) {
cumsum[i] = cumsum[i - 1] + buckets[i - 1];
}
// Distribute elements
for (int i = left; i <= right; i++) {
int digit = (arr[i] / exp) % 10;
temp[cumsum[digit]++] = arr[i];
}
// Copy back
for (int i = left; i <= right; i++) {
arr[i] = temp[i - left];
}
free(temp);
// Recursively sort each bucket
int start = left;
for (int i = 0; i < 10; i++) {
if (buckets[i] > 0) {
radix_sort_msd_recursive(arr, start, start + buckets[i] - 1, exp / 10);
start += buckets[i];
}
}
}
void radix_sort_msd(int arr[], int n) {
int max = get_max(arr, n);
int exp = 1;
while (max / exp >= 10) exp *= 10;
radix_sort_msd_recursive(arr, 0, n - 1, exp);
}

Time Complexity: O(d * (n + k)) where d is digits
Space Complexity: O(n + k)
Stable: Yes
When to use: Large integer ranges, fixed-width keys

---

9. Bucket Sort

Bucket Sort distributes elements into buckets and sorts each bucket.

#include <stdlib.h>
#include <math.h>
// Node for bucket list
typedef struct BucketNode {
double value;
struct BucketNode *next;
} BucketNode;
void bucket_sort(double arr[], int n) {
if (n <= 1) return;
// Create buckets
BucketNode **buckets = (BucketNode **)calloc(n, sizeof(BucketNode *));
// Distribute elements
for (int i = 0; i < n; i++) {
int bucket_index = (int)(n * arr[i]);  // Assume arr[i] in [0, 1)
BucketNode *new_node = (BucketNode *)malloc(sizeof(BucketNode));
new_node->value = arr[i];
new_node->next = NULL;
// Insert in sorted order
if (buckets[bucket_index] == NULL || 
buckets[bucket_index]->value > arr[i]) {
new_node->next = buckets[bucket_index];
buckets[bucket_index] = new_node;
} else {
BucketNode *current = buckets[bucket_index];
while (current->next != NULL && current->next->value < arr[i]) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
// Collect results
int index = 0;
for (int i = 0; i < n; i++) {
BucketNode *current = buckets[i];
while (current != NULL) {
arr[index++] = current->value;
BucketNode *temp = current;
current = current->next;
free(temp);
}
}
free(buckets);
}
// Integer bucket sort
void bucket_sort_int(int arr[], int n) {
if (n <= 1) return;
int max = arr[0], min = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
int range = max - min + 1;
int *count = (int *)calloc(range, sizeof(int));
for (int i = 0; i < n; i++) {
count[arr[i] - min]++;
}
int index = 0;
for (int i = 0; i < range; i++) {
while (count[i]-- > 0) {
arr[index++] = i + min;
}
}
free(count);
}

Time Complexity: O(n + k) average, O(n²) worst
Space Complexity: O(n)
Stable: Yes (with proper implementation)
When to use: Uniformly distributed data

---

Part 4: Hybrid and Advanced Sorts

10. Timsort (Python's Sorting Algorithm)

Timsort combines merge sort with insertion sort, optimized for real-world data.

#include <stdlib.h>
#include <string.h>
#define MIN_MERGE 32
#define MIN_GALLOP 7
typedef struct {
int *base;
int len;
} Run;
// Binary insertion sort for small runs
void insertion_sort_run(int arr[], int left, int right) {
for (int i = left + 1; i <= right; i++) {
int key = arr[i];
int j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// Merge two runs
void tim_merge(int arr[], int left, int mid, int right, int *temp) {
int len1 = mid - left + 1;
int len2 = right - mid;
memcpy(temp + left, arr + left, (len1 + len2) * sizeof(int));
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k++] = temp[i++];
} else {
arr[k++] = temp[j++];
}
}
while (i <= mid) arr[k++] = temp[i++];
while (j <= right) arr[k++] = temp[j++];
}
// Find next run (natural run or create with insertion sort)
int find_run(int arr[], int n, int start) {
int end = start + 1;
if (end >= n) return start;
// Check if run is increasing or decreasing
if (arr[start] <= arr[end]) {
// Increasing run
while (end + 1 < n && arr[end] <= arr[end + 1]) {
end++;
}
} else {
// Decreasing run - reverse it
while (end + 1 < n && arr[end] >= arr[end + 1]) {
end++;
}
// Reverse the run
int i = start, j = end;
while (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// If run is too short, extend with insertion sort
if (end - start + 1 < MIN_MERGE) {
end = (start + MIN_MERGE - 1 < n - 1) ? start + MIN_MERGE - 1 : n - 1;
insertion_sort_run(arr, start, end);
}
return end;
}
// Timsort implementation
void timsort(int arr[], int n) {
if (n <= 1) return;
int *temp = (int *)malloc(n * sizeof(int));
Run *stack = (Run *)malloc(n * sizeof(Run));
int stack_size = 0;
int start = 0;
while (start < n) {
int end = find_run(arr, n, start);
stack[stack_size++] = (Run){arr + start, end - start + 1};
start = end + 1;
// Merge runs to maintain stack invariants
while (stack_size > 1) {
Run *x = &stack[stack_size - 2];
Run *y = &stack[stack_size - 1];
if (stack_size > 2 && stack[stack_size - 3].len <= x->len + y->len) {
// Merge the smaller of x and y with z
if (stack[stack_size - 3].len < y->len) {
tim_merge(arr, 
(int)(stack[stack_size - 3].base - arr),
(int)(stack[stack_size - 3].base - arr + stack[stack_size - 3].len - 1),
(int)(y->base - arr + y->len - 1),
temp);
stack[stack_size - 3].len += stack[stack_size - 2].len + stack[stack_size - 1].len;
stack_size -= 2;
} else {
tim_merge(arr,
(int)(x->base - arr),
(int)(x->base - arr + x->len - 1),
(int)(y->base - arr + y->len - 1),
temp);
x->len += y->len;
stack_size--;
}
} else if (x->len <= y->len) {
tim_merge(arr,
(int)(x->base - arr),
(int)(x->base - arr + x->len - 1),
(int)(y->base - arr + y->len - 1),
temp);
x->len += y->len;
stack_size--;
} else {
break;
}
}
}
// Merge remaining runs
while (stack_size > 1) {
tim_merge(arr,
(int)(stack[stack_size - 2].base - arr),
(int)(stack[stack_size - 2].base - arr + stack[stack_size - 2].len - 1),
(int)(stack[stack_size - 1].base - arr + stack[stack_size - 1].len - 1),
temp);
stack[stack_size - 2].len += stack[stack_size - 1].len;
stack_size--;
}
free(temp);
free(stack);
}

---

Part 5: Utility Functions and Testing

Array Utilities

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
// Print array
void print_array(int arr[], int n) {
printf("[");
for (int i = 0; i < n; i++) {
printf("%d", arr[i]);
if (i < n - 1) printf(", ");
}
printf("]\n");
}
// Generate random array
void random_array(int arr[], int n, int min, int max) {
for (int i = 0; i < n; i++) {
arr[i] = min + rand() % (max - min + 1);
}
}
// Generate sorted array
void sorted_array(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = i;
}
}
// Generate reverse sorted array
void reverse_array(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = n - i;
}
}
// Check if array is sorted
bool is_sorted(int arr[], int n) {
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) return false;
}
return true;
}
// Copy array
void copy_array(int src[], int dest[], int n) {
for (int i = 0; i < n; i++) {
dest[i] = src[i];
}
}
// Compare arrays
bool compare_arrays(int a[], int b[], int n) {
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) return false;
}
return true;
}

Benchmarking Framework

#include <stdio.h>
#include <time.h>
typedef void (*SortFunction)(int[], int);
// Measure execution time
double measure_time(SortFunction sort, int arr[], int n, int *result) {
int *copy = (int *)malloc(n * sizeof(int));
copy_array(arr, copy, n);
clock_t start = clock();
sort(copy, n);
clock_t end = clock();
*result = is_sorted(copy, n);
double time = (double)(end - start) / CLOCKS_PER_SEC * 1000; // milliseconds
free(copy);
return time;
}
// Benchmark a sorting algorithm
void benchmark(const char *name, SortFunction sort, int arr[], int n, int iterations) {
double total_time = 0;
int successes = 0;
for (int i = 0; i < iterations; i++) {
int result;
double time = measure_time(sort, arr, n, &result);
total_time += time;
if (result) successes++;
}
double avg_time = total_time / iterations;
printf("%-20s: avg %.3f ms, %d/%d successful\n", 
name, avg_time, successes, iterations);
}
// Run all benchmarks
void run_benchmarks(int arr[], int n, int iterations) {
printf("\n=== Sorting Benchmarks (n=%d, iterations=%d) ===\n", n, iterations);
benchmark("Bubble Sort", (SortFunction)bubble_sort, arr, n, iterations);
benchmark("Selection Sort", (SortFunction)selection_sort, arr, n, iterations);
benchmark("Insertion Sort", (SortFunction)insertion_sort, arr, n, iterations);
benchmark("Shell Sort", (SortFunction)shell_sort, arr, n, iterations);
benchmark("Merge Sort", (SortFunction)merge_sort_wrapper, arr, n, iterations);
benchmark("Quick Sort", (SortFunction)quick_sort_wrapper, arr, n, iterations);
benchmark("Heap Sort", (SortFunction)heap_sort, arr, n, iterations);
benchmark("Counting Sort", (SortFunction)counting_sort, arr, n, iterations);
benchmark("Radix Sort", (SortFunction)radix_sort_lsd, arr, n, iterations);
benchmark("Timsort", (SortFunction)timsort, arr, n, iterations);
}
// Wrappers for functions with different signatures
void merge_sort_wrapper(int arr[], int n) {
merge_sort(arr, 0, n - 1);
}
void quick_sort_wrapper(int arr[], int n) {
quick_sort(arr, 0, n - 1);
}

Complete Test Program

int main() {
srand(time(NULL));
const int SIZE = 10000;
const int ITERATIONS = 10;
int *original = (int *)malloc(SIZE * sizeof(int));
printf("Testing with random data:\n");
random_array(original, SIZE, 0, 10000);
run_benchmarks(original, SIZE, ITERATIONS);
printf("\nTesting with sorted data:\n");
sorted_array(original, SIZE);
run_benchmarks(original, SIZE, ITERATIONS);
printf("\nTesting with reverse sorted data:\n");
reverse_array(original, SIZE);
run_benchmarks(original, SIZE, ITERATIONS);
printf("\nTesting with nearly sorted data:\n");
sorted_array(original, SIZE);
for (int i = 0; i < SIZE / 100; i++) {
int idx1 = rand() % SIZE;
int idx2 = rand() % SIZE;
int temp = original[idx1];
original[idx1] = original[idx2];
original[idx2] = temp;
}
run_benchmarks(original, SIZE, ITERATIONS);
free(original);
return 0;
}

---

Summary: Choosing the Right Algorithm

Scenario	Recommended Algorithm
Small arrays (< 50)	Insertion Sort
Nearly sorted data	Insertion Sort, Timsort
Large general-purpose	Quick Sort, Timsort
Stable sort required	Merge Sort, Timsort
Guaranteed O(n log n)	Merge Sort, Heap Sort
Memory constrained	Heap Sort, Quick Sort
Small integer range	Counting Sort
Large integer range	Radix Sort
Uniform distribution	Bucket Sort
Linked lists	Merge Sort

---

Conclusion

Sorting algorithms form the foundation of efficient computing. Understanding their characteristics—time complexity, space requirements, stability, and adaptability—allows you to select the right tool for your specific needs. From the simplicity of bubble sort to the sophistication of Timsort, each algorithm offers unique trade-offs between performance, memory usage, and implementation complexity.

The key to mastery is not memorizing implementations but understanding the principles: divide and conquer, recursion, heap structures, and distribution strategies. With this knowledge, you can implement efficient sorting in any context, optimize for your specific data characteristics, and even design custom sorting solutions when needed.