#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Utility: Print Array
void printArray(int arr[], int n) {
    for(int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 1. SHELL SORT
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];
            int j;
            for (j = i; j >= gap && arr[j-gap] > temp; j -= gap)
                arr[j] = arr[j-gap];
            arr[j] = temp;
        }
    }
}

// 2. QUICK SORT
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for(int j = low; j < high; 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]; arr[high] = temp;
    return i+1;
}

void quickSort(int arr[], int low, int high) {
    if(low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}

// 3. MERGE SORT
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) {
        if(L[i] <= R[j]) arr[k++] = L[i++];
 Internazionale        else arr[k++] = 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-l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

// 4. HEAP SORT
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);
    }
}

void heapSort(int arr[], int n) {
    for(int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for(int i = n-1; i > 0; i--) {
        int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
        heapify(arr, i, 0);
    }
}

// 5. COUNTING SORT (Linear Time)
void countingSort(int arr[], int n, int max) {
    int count[max+1], output[n];
    for(int i = 0; i <= max; i++) count[i] = 0;
    for(int i = 0; i < n; i++) count[arr[i]]++;
    for(int i = 1; i <= max; i++) count[i] += count[i-1];

    for(int i = n-1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    for(int i = 0; i < n; i++) arr[i] = output[i];
}

// Main function to test all
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90, 88, 15, 45};
    int n = 10;

    printf("Original: ");
    printArray(arr, n);

    // Test each sort one by one (uncomment one)

    // shellSort(arr, n);
    // quickSort(arr, 0, n-1);
    // mergeSort(arr, 0, n-1);
    // heapSort(arr, n);
    // countingSort(arr, n, 90);  // max value = 90

    printf("Sorted:   ");
    printArray(arr, n);

    return 0;
}

Time →
↑
│        ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆   ← Exponential O(2^n)
│      ◆
│     ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆     ← Quadratic O(n²)
│    ◆
│   ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆       ← n log n (Merge, Quick, Heap)
│  ◆
│ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆         ← Linear O(n)
│◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆   ← Constant O(1)
└───────────────────────────────────→ Size (n)
     1   10   100   1000  10⁴  10⁶  10⁸

1. Quick Sort      ★★★★★ (Fastest in practice)
2. Merge Sort      ★★★★☆
3. Heap Sort       ★★★☆☆
4. Shell Sort      ★★★☆☆
5. Counting Sort   ★★★★★★ (if range is small)

Original: 64 34 25 12 22 11 90 88 15 45
Sorted:   11 12 15 22 25 34 45 64 88 90