C Implementations of Core Sorting Algorithms

Fundamental Sorting Algorithms in C

This document provides standard C implementations for three essential comparison-based sorting algorithms: Merge Sort, Quick Sort, and Heap Sort. These examples demonstrate the core logic and structure of each algorithm.

Merge Sort Implementation

Merge Sort is a stable, divide-and-conquer algorithm known for its consistent O(n log n) time complexity.

#include <stdio.h>

void merge(int a[], int l, int m, int r) {
    int i=l, j=m+1, k=0, b[100];
    while(i<=m && j<=r) {
        if(a[i]<a[j]) b[k++]=a[i++];
        else b[k++]=a[j++];
    }
    while(i<=m) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(i=l,k=0;i<=r;i++,k++) a[i]=b[k];
}

void mergesort(int a[], int l, int r) {
    if(l<r) {
        int m=(l+r)/2;
        mergesort(a,l,m);
        mergesort(a,m+1,r);
        merge(a,l,m,r);
    }
}

int main() {
    int a[100],n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    mergesort(a,0,n-1);
    for(i=0;i<n;i++) printf("%d ",a[i]);
    return 0;
}

Quick Sort Implementation

Quick Sort is an efficient, in-place, comparison-based algorithm, often faster in practice than Merge Sort, though its worst-case complexity is O(n²).

#include <stdio.h>

void swap(int *a, int *b){
    int t=*a;*a=*b;*b=t;
}

int partition(int a[],int low,int high){
    int pivot=a[high],i=low-1;
    for(int j=low;j<high;j++){
        if(a[j]<pivot){
            i++;
            swap(&a[i],&a[j]);
        }
    }
    swap(&a[i+1],&a[high]);
    return i+1;
}

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

int main(){
    int n,a[100];
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    quicksort(a,0,n-1);
    for(int i=0;i<n;i++) printf("%d ",a[i]);
    return 0;
}

Heap Sort Implementation

Heap Sort uses a binary heap data structure to sort elements. It guarantees an O(n log n) time complexity and is an in-place algorithm.

#include <stdio.h>

void heapify(int a[], int n, int i) {
    int largest = i, l = 2*i + 1, r = 2*i + 2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest != i) {
        int t = a[i]; a[i] = a[largest]; a[largest] = t;
        heapify(a, n, largest);
    }
}

void heapsort(int a[], int n) {
    for (int i = n/2 - 1; i >= 0; i--) heapify(a, n, i);
    for (int i = n - 1; i > 0; i--) {
        int t = a[0]; a[0] = a[i]; a[i] = t;
        heapify(a, i, 0);
    }
}

int main() {
    int n, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    heapsort(a, n);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}