October 17, 2026

1. Introduction to Sorting Algorithms

What Is Sorting?

Sorting is the process of arranging data in a particular order, usually ascending or descending.

For example, the following array is unsorted:

[50, 20, 40, 10, 30]

After sorting in ascending order:

[10, 20, 30, 40, 50]

After sorting in descending order:

[50, 40, 30, 20, 10]

Why Do We Need Sorting?

Sorting is useful because it can make data easier to search, analyze, compare, and display.

Common applications include:

• Arranging student marks from highest to lowest.

• Sorting products by price.

• Organizing names alphabetically.

• Ranking players by score.

• Preparing data for efficient searching algorithms.

Types of Sorting Algorithms

In this module, we will study six important sorting algorithms:

1. Bubble Sort

2. Selection Sort

3. Insertion Sort

4. Merge Sort

5. Quick Sort

6. Heap Sort

Each algorithm sorts data differently and has its own advantages and disadvantages.

2. Bubble Sort in C

What Is Bubble Sort?

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

After each complete pass, the largest unsorted element moves to its correct position at the end of the array when sorting in ascending order.

Example

Consider this array:

[5, 3, 8, 2, 1]

Pass 1:

• Compare 5 and 3 → swap.

• Compare 5 and 8 → no swap.

• Compare 8 and 2 → swap.

• Compare 8 and 1 → swap.

Array after Pass 1:

[3, 5, 2, 1, 8]

Pass 2:

[3, 2, 1, 5, 8]

Pass 3:

[2, 1, 3, 5, 8]

Pass 4:

[1, 2, 3, 5, 8]

The array is now sorted.

Bubble Sort Program in C

#include 

int main(void) {
    int arr[] = {5, 3, 8, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int i, j, temp;
    int swapped;

    for (i = 0; i < n - 1; i++) {
        swapped = 0;

        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }

        if (swapped == 0) {
            break;
        }
    }

    printf("Sorted array: ");

    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    printf("\n");
    return 0;
}

Output:

Sorted array: 1 2 3 5 8

Bubble Sort Complexity

• Best case: (O(n)), when the array is already sorted and the early-exit optimization is used.

• Average case: (O(n^2)).

• Worst case: (O(n^2)).

• Auxiliary space: (O(1)).

Key point: Bubble Sort is easy to understand, but it is inefficient for large datasets.

3. Selection Sort in C

What Is Selection Sort?

Selection Sort repeatedly finds the smallest element in the unsorted portion of the array and places it at the beginning of that portion.

For ascending order, the algorithm selects the minimum element during each pass.

Example

Initial array:

[64, 25, 12, 22, 11]

Pass 1: The smallest element is 11. Swap it with 64.

[11, 25, 12, 22, 64]

Pass 2: The smallest remaining element is 12.

[11, 12, 25, 22, 64]

Pass 3: The smallest remaining element is 22.

[11, 12, 22, 25, 64]

Pass 4: The remaining elements are already in order.

[11, 12, 22, 25, 64]

Selection Sort Program in C

#include 

int main(void) {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int i, j, minIndex, temp;

    for (i = 0; i < n - 1; i++) {
        minIndex = i;

        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    printf("Sorted array: ");

    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    printf("\n");
    return 0;
}

Output:

Sorted array: 11 12 22 25 64

Selection Sort Complexity

• Best case: (O(n^2)).

• Average case: (O(n^2)).

• Worst case: (O(n^2)).

• Auxiliary space: (O(1)).

Selection Sort performs roughly the same number of comparisons even when the input is already sorted. However, it makes at most (n-1) swaps in this implementation.

Key point: Selection Sort can be useful when minimizing swaps matters, but it is still slow for large arrays.

4. Insertion Sort in C

What Is Insertion Sort?

Insertion Sort builds a sorted portion of the array one element at a time.

It takes the next element, called the key, and inserts it into the correct position among the elements already sorted.

This is similar to arranging playing cards in your hand.

Example

Initial array:

[5, 3, 4, 1, 2]

Step 1: Insert 3 before 5.

[3, 5, 4, 1, 2]

Step 2: Insert 4 between 3 and 5.

[3, 4, 5, 1, 2]

Step 3: Insert 1 at the beginning.

[1, 3, 4, 5, 2]

Step 4: Insert 2 after 1.

[1, 2, 3, 4, 5]

Insertion Sort Program in C

#include 

int main(void) {
    int arr[] = {5, 3, 4, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int i, j, key;

    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }

    printf("Sorted array: ");

    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    printf("\n");
    return 0;
}

Output:

Sorted array: 1 2 3 4 5

Insertion Sort Complexity

• Best case: (O(n)), when the array is already sorted.

• Average case: (O(n^2)).

• Worst case: (O(n^2)).

• Auxiliary space: (O(1)).

Key point: Insertion Sort works well for small arrays and nearly sorted data. It is also a stable sorting algorithm when implemented as shown.

5. Merge Sort in C

What Is Merge Sort?

Merge Sort is a divide-and-conquer sorting algorithm.

It divides an array into smaller parts, sorts those parts recursively, and merges the sorted parts into a single sorted array.

It follows three main steps:

1. Divide: Split the array into two halves.

2. Conquer: Recursively sort each half.

3. Combine: Merge the two sorted halves.

Example

Initial array:

[38, 27, 43, 3, 9, 82, 10]

Divide the array into smaller sections:

[38, 27, 43, 3]   [9, 82, 10]

Continue dividing until each section contains one element. Then merge the sections in sorted order.

Final result:

[3, 9, 10, 27, 38, 43, 82]

Merge Sort Program in C

#include 

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    int i, j, k;

    for (i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }

    for (j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    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++];
        }
    }

    while (i < n1) {
        arr[k++] = L[i++];
    }

    while (j < n2) {
        arr[k++] = R[j++];
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main(void) {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int i;

    mergeSort(arr, 0, n - 1);

    printf("Sorted array: ");

    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    printf("\n");
    return 0;
}

Output:

Sorted array: 3 9 10 27 38 43 82

Note: This example uses variable-length arrays for the temporary merge buffers, supported by C99 implementations. If your compiler does not support variable-length arrays, use dynamically allocated buffers or fixed-size arrays appropriate to the problem.

Merge Sort Complexity

• Best case: (O(n \log n)).

• Average case: (O(n \log n)).

• Worst case: (O(n \log n)).

• Auxiliary space: (O(n)) for the temporary merge buffers in this array implementation.

Key point: Merge Sort provides predictable performance and is useful for large datasets. Its standard array implementation requires extra memory.

6. Quick Sort in C

What Is Quick Sort?

Quick Sort is another divide-and-conquer algorithm. It chooses an element called the pivot, partitions the array around that pivot, and recursively sorts the resulting sections.

In the implementation below, the last element is selected as the pivot.

After partitioning:

• Elements less than or equal to the pivot are placed on its left.

• Elements greater than the pivot are placed on its right.

• The pivot reaches its final sorted position.

Example

Initial array:

[10, 7, 8, 9, 1, 5]

Choose 5 as the pivot. After partitioning, the array becomes:

[1, 5, 8, 9, 10, 7]

The pivot 5 is now in its correct position. Quick Sort then sorts the left and right sections recursively.

Final sorted array:

[1, 5, 7, 8, 9, 10]

Quick Sort Program in C

#include 

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    int j;

    for (j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            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 pivotIndex = partition(arr, low, high);

        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main(void) {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int i;

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");

    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    printf("\n");
    return 0;
}

Output:

Sorted array: 1 5 7 8 9 10

Quick Sort Complexity

• Best case: (O(n \log n)).

• Average case: (O(n \log n)).

• Worst case: (O(n^2)), when partitioning repeatedly produces highly unbalanced sections.

• Auxiliary space: (O(\log n)) on average for recursion; worst-case recursion depth can reach (O(n)).

Key point: Quick Sort is often fast in practice, but pivot selection strongly affects its performance. Randomized or median-based pivot strategies can reduce the chance of consistently poor partitions.

7. Heap Sort in C

What Is Heap Sort?

Heap Sort uses a binary heap to sort an array.

For ascending order, it commonly uses a max heap, in which every parent node is greater than or equal to its children.

For an array using zero-based indexing:

• Left child of index i: 2 * i + 1

• Right child of index i: 2 * i + 2

• Parent of index i: (i - 1) / 2 for i > 0

Heap Sort works in two main stages:

1. Build a max heap from the array.

2. Swap the root (largest element) with the last element in the heap, reduce the heap size, and restore the max-heap property.

Repeat until the array is sorted.

Example

Initial array:

[4, 10, 3, 5, 1]

Build a max heap. One valid heap representation is:

[10, 5, 3, 4, 1]

Move the maximum element to the end and restore the heap repeatedly.

Final sorted array:

[1, 3, 4, 5, 10]

Heap Sort Program in C

#include 

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

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) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    int i;

    for (i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    for (i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

int main(void) {
    int arr[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int i;

    heapSort(arr, n);

    printf("Sorted array: ");

    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    printf("\n");
    return 0;
}

Output:

Sorted array: 1 3 4 5 10

Heap Sort Complexity

• Best case: (O(n \log n)).

• Average case: (O(n \log n)).

• Worst case: (O(n \log n)).

• Auxiliary space: (O(1)) for the iterative heap-building and extraction process, excluding the recursion stack used by heapify. The recursive heapify shown here can use up to (O(\log n)) stack space.

Key point: Heap Sort has guaranteed (O(n \log n)) time and can sort in place, but it is not stable in its standard form.

8. Sorting Algorithm Comparison

Different sorting algorithms are useful in different situations. The best choice depends on the size of the dataset, memory constraints, input order, and required guarantees.

*Bubble Sort's best case assumes the early-exit optimization used in this tutorial.

Stability Comparison

A sorting algorithm is stable if equal elements retain their original relative order.

• Bubble Sort: Stable in the implementation shown.

• Selection Sort: Generally unstable.

• Insertion Sort: Stable in the implementation shown.

• Merge Sort: Stable when equal elements are merged in original order, as in the implementation shown.

• Quick Sort: Generally unstable.

• Heap Sort: Generally unstable.

Which Sorting Algorithm Should You Choose?

• Bubble Sort: For learning the basic idea of comparing and swapping adjacent elements.

• Selection Sort: When you want a simple algorithm with few swaps.

• Insertion Sort: For small or nearly sorted arrays.

• Merge Sort: When guaranteed (O(n \log n)) time and stability are important and extra memory is acceptable.

• Quick Sort: For fast average-case performance on arrays when a suitable pivot strategy is used.

• Heap Sort: When guaranteed (O(n \log n)) time and low auxiliary array memory are priorities.

9. Final Summary

In this module, we learned six important sorting algorithms in C:

1. Bubble Sort repeatedly swaps adjacent elements that are out of order.

2. Selection Sort selects the minimum element from the unsorted section.

3. Insertion Sort inserts each element into its correct position in a sorted section.

4. Merge Sort divides the array, sorts each half, and merges the results.

5. Quick Sort partitions the array around a pivot and recursively sorts the partitions.

6. Heap Sort builds a heap and repeatedly extracts its maximum element.

The most important concept is understanding not only how each algorithm works, but also how its time complexity, memory requirements, and stability affect its practical use.