Overview of Sorting Algorithms

Sorting algorithms rearrange a collection of elements into a specific order—typically ascending or descending. These algorithms are broadly categorized as:

• Internal sorting: All data fits into main memory. Examples include insertion sort (direct and Shell), selection sort (simple and heap), exchange-based sorts (bubble and quicksort), merge sort, and radix sort.
• External sorting: Used when data volume exceeds available memory, rqeuiring intermediate storage on disk.

Time Complexity Analysis

Algorithm efficiency is commonly evaluated using asymptotic time complexity, denoted as O(f(n)), which describes how runtime scales with input size n.

To derive time complexity:

1. Replace constant-time operations with 1.
2. Retain only the highest-order term.
3. Discard leading coefficients.

Common complexity classes include:

• O(1): Constant time (e.g., accessing an array element).
• O(log n): Logarithmic time (e.g., binary search).
• O(n): Linear time (e.g., single loop over n items).
• O(n log n): Linearithmic time (e.g., nested loop with logarithmic inner loop).
• O(n²): Quadratic time (e.g., two nested loops).

Most algorithm analyses focus on worst-case time complexity, as it provides an upper bound on performance.

Space Complexity

Space complexity measures the amount of additional memory an algorithm uses relative to input size. While time complexity is usually prioritized, space matters in memory-constrained environments. For example, merge sort and quikcsort require O(log n) or O(n) auxiliary space due to recursion.

Bubble Sort

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process continues until no swaps occur.

int[] data = {3, 9, -1, 10, -2};
boolean swapped;
for (int pass = 0; pass < data.length - 1; pass++) {
    swapped = false;
    for (int i = 0; i < data.length - pass - 1; i++) {
        if (data[i] > data[i + 1]) {
            int tmp = data[i];
            data[i] = data[i + 1];
            data[i + 1] = tmp;
            swapped = true;
        }
    }
    if (!swapped) break; // Early termination if sorted
}

Selection Sort

Selection sort divides the array into a sorted and unsorted region. It repeatedly selects the smallest element from the unsorted region and swaps it into place.

int[] data = {1, 5, 2, 4, 7};
for (int i = 0; i < data.length - 1; i++) {
    int minIdx = i;
    for (int j = i + 1; j < data.length; j++) {
        if (data[j] < data[minIdx]) {
            minIdx = j;
        }
    }
    if (minIdx != i) {
        int tmp = data[i];
        data[i] = data[minIdx];
        data[minIdx] = tmp;
    }
}

Insertion Sort

Inserrtion sort builds the final sorted array one item at a time by inserting each new element into its correct position within the already-sorted portion.

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int pos = i - 1;
        while (pos >= 0 && arr[pos] > key) {
            arr[pos + 1] = arr[pos];
            pos--;
        }
        arr[pos + 1] = key;
    }
}

Shell Sort

Shell sort improves insertion sort by comparing elements separated by a gap that reduces over time. It performs insertion sort on subarrays defined by decreasing gaps.

public static void shellSort(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

Quick Sort

Quicksort uses a divide-and-conquer approach: it selects a pivot, partitions the array so that elements less than the pivot come before it and greater ones after, then recursively sorts the partitions.

public static 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);
    }
}

private static 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 tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    int tmp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = tmp;
    return i + 1;
}

Merge Sort

Merge sort recursively splits the array into halves, sorts each half, and merges them back in order. It guarantees O(n log n) time but requires O(n) extra space.

public static void mergeSort(int[] arr, int left, int right, int[] buffer) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid, buffer);
        mergeSort(arr, mid + 1, right, buffer);
        merge(arr, left, mid, right, buffer);
    }
}

private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    System.arraycopy(temp, 0, arr, left, k);
}

Radix Sort

Radix sort processes integers digit by digit from least significant to most, using bucket distribution. It is stable and efficient for fixed-length keys but uses significant extra memory.

public static void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().orElse(0);
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

private static void countingSortByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10];

    for (int value : arr) {
        count[(value / exp) % 10]++;
    }
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    for (int i = n - 1; i >= 0; i--) {
        output[--count[(arr[i] / exp) % 10]] = arr[i];
    }
    System.arraycopy(output, 0, arr, 0, n);
}

Algorithm Comparison

*Shell sort’s complexity depends on the gap sequence.
In-Place: Uses minimal extra memory.
Stable: Preserves relative order of equal elements.