Concept of Sorting

Sorting: The process of arranging a sequence of records in increasing or decreasing order based on one or more keys.

Stability: If two records have equal keys and their relative order is preserved after sorting, the algorithm is stable; otherwise, it is unstable.

Internal Sorting: All data elements are stored in memory during sorting.

External Sorting: Data elements are too numerous to fit in memory at once, requiring movement between internal and external storage during sorting.

1. Insertion Sort

void insertionSort(int* arr, int n) {
    for (int i = 0; i < n - 1; ++i) {
        int end = i;
        while (end >= 0) {
            if (arr[end + 1] < arr[end]) {
                swap(&arr[end + 1], &arr[end]);
                --end;
            } else {
                break;
            }
        }
    }
}

Isnertion sort works by inserting a record into an already sorted list, resulting in a new sorted list with one more record.

Code Explanation:

• The loop i < n-1 prevents end+1 from exceeding array bounds.
• end-- allows the new element to compare with previous elements until it finds its correct position. When end < 0, the loop stops.

2. Shell Sort

Shell sort improves insertion sort by pre-sorting the data with a gap, reducing time complexity.

void shellSort(int* arr, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1;
        for (int j = 0; j < gap; ++j) {
            for (int i = j; i < n - gap; i += gap) {
                int end = i;
                while (end >= 0) {
                    if (arr[end + gap] < arr[end]) {
                        swap(&arr[end + gap], &arr[end]);
                        end -= gap;
                    } else {
                        break;
                    }
                }
            }
        }
    }
}

Shell sort divides data into gap groups, sorting elements with a gap enterval to avoid worst-case scenarios. The gap decreases gradually, making the data more ordered before final insertion sort (gap = 1).

• gap = gap/3 + 1 ensures the last gap is 1.
• The outer j loop differentiates groups.
• The inner loops handle sorting within each group, similar to insertion sort but with gap increments.
• i < n - gap prevents array out-of-bounds during comparisons.

3. Selection Sort

Selection sort is a brute-force algorithm that repeatedly selects the smallest and largest elements and places them at the ends.

void selectionSort(int* arr, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        int min = begin, max = end;
        for (int i = begin; i <= end; ++i) {
            if (arr[i] < arr[min]) min = i;
            if (arr[i] > arr[max]) max = i;
        }
        swap(&arr[min], &arr[begin]);
        if (max == begin) {
            max = min; // update max if it was swapped
        }
        swap(&arr[max], &arr[end]);
        ++begin;
        --end;
    }
}

Key: track indices of smallest and largest elements. After swapping the smallest with the first position, if the largest was at the first position, update its index to the smallest's new location.

4. Quick Sort

4.1 Hoare Partition

int medianOfThree(int* arr, int left, int right) {
    int mid = (left + right) / 2;
    if (arr[left] < arr[mid]) {
        if (arr[mid] < arr[right]) return mid;
        else if (arr[left] < arr[right]) return right;
        else return left;
    } else {
        if (arr[mid] > arr[right]) return mid;
        else if (arr[left] < arr[right]) return left;
        else return right;
    }
}

void quickSortHoare(int* arr, int left, int right) {
    if (left >= right) return;
    if (right - left + 1 < 10) {
        insertionSort(arr + left, right - left + 1);
        return;
    }
    int mid = medianOfThree(arr, left, right);
    swap(&arr[mid], &arr[left]);
    int begin = left, end = right;
    int key = left;
    while (begin < end) {
        while (begin < end && arr[end] >= arr[key]) --end;
        while (begin < end && arr[begin] <= arr[key]) ++begin;
        swap(&arr[begin], &arr[end]);
    }
    swap(&arr[begin], &arr[key]);
    key = begin;
    quickSortHoare(arr, left, key - 1);
    quickSortHoare(arr, key + 1, right);
}

• For small arrays (size < 10), use insertion sort to avoid excessive recursion overhead.
• Median-of-three selects a pivot that is not the min or max to avoid worst-case O(n²).
• The Hoare partition moves from both ends: right finds elements smaller than pivot, left finds larger, then swap.
• When pointers meet, the meeting point has a value less than the pivot, so swap with pivot.

4.2 Two-Pointer Partition

int twoPointerPartition(int* arr, int left, int right) {
    int key = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right) {
        if (arr[cur] < arr[key] && ++prev != cur) {
            swap(&arr[prev], &arr[cur]);
        }
        ++cur;
    }
    swap(&arr[key], &arr[prev]);
    return prev;
}

• Uses two indices: prev and cur. cur moves forward; when it finds an element smaller than the pivot and prev is not adjacent, swap.
• After the loop, swap pivot with prev.

4.3 Non-Recursive Quick Sort

void quickSortNonRecursive(int* arr, int left, int right) {
    Stack s;
    initStack(&s);
    push(&s, right);
    push(&s, left);
    while (!isEmpty(&s)) {
        int start = top(&s); pop(&s);
        int end = top(&s); pop(&s);
        int pivot = twoPointerPartition(arr, start, end);
        if (pivot + 1 < end) {
            push(&s, end);
            push(&s, pivot + 1);
        }
        if (start < pivot - 1) {
            push(&s, pivot - 1);
            push(&s, start);
        }
    }
    destroyStack(&s);
}

• Simulates recursion using a stack. Push initial left and right indices, then process intervals.
• Order of pushing/popping must be consistent; here we push right first then left, so we pop left first.

5. Merge Sort

5.1 Recursive Merge Sort

void mergeHelper(int* arr, int* tmp, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeHelper(arr, tmp, left, mid);
    mergeHelper(arr, tmp, mid + 1, right);
    int i = left;
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    while (begin1 <= end1 && begin2 <= end2) {
        if (arr[begin1] < arr[begin2]) tmp[i++] = arr[begin1++];
        else tmp[i++] = arr[begin2++];
    }
    while (begin1 <= end1) tmp[i++] = arr[begin1++];
    while (begin2 <= end2) tmp[i++] = arr[begin2++];
    memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1));
}

void mergeSort(int* arr, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (!tmp) { perror("malloc"); return; }
    mergeHelper(arr, tmp, 0, n - 1);
    free(tmp);
}

• Recursively divides the array into halves until subarrays of size 1, then merges them in sorted order using a temporary array.
• The merge step compares elements from two sorted halves and copies the smaller one into tmp.
• Finally, copy tmp back to arr.

5.2 Non-Recursive Merge Sort

void mergeSortNonRecursive(int* arr, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (!tmp) { perror("malloc"); return; }
    int gap = 1;
    while (gap < n) {
        for (int i = 0; i < n; i += 2 * gap) {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            if (begin2 >= n) break; // no second subarray
            if (end2 >= n) end2 = n - 1; // adjust end
            int j = i;
            while (begin1 <= end1 && begin2 <= end2) {
                if (arr[begin1] < arr[begin2]) tmp[j++] = arr[begin1++];
                else tmp[j++] = arr[begin2++];
            }
            while (begin1 <= end1) tmp[j++] = arr[begin1++];
            while (begin2 <= end2) tmp[j++] = arr[begin2++];
            memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
        }
        gap *= 2;
    }
    free(tmp);
}

• Iteratively merges subarrays of size gap, doubling each iteration.
• Handles boundary cases where begin2 or end2 may exceed array length.

6. Non-Comparison Sort (Counting Sort)

void countingSort(int* arr, int n) {
    if (n <= 0) return;
    int min = arr[0], max = arr[0];
    for (int i = 1; i < n; ++i) {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }
    int range = max - min + 1;
    int* count = (int*)calloc(range, sizeof(int));
    if (!count) { perror("calloc"); return; }
    for (int i = 0; i < n; ++i) {
        count[arr[i] - min]++;
    }
    int j = 0;
    for (int i = 0; i < range; ++i) {
        while (count[i]--) {
            arr[j++] = i + min;
        }
    }
    free(count);
}

• Counts occurrences of each distinct value using an array indexed by value offset.
• Then overwrites the original array with sorted values.
• Works best when the range of values is not too large.