Direct Insertion Sort

This algorithm treats the first element of the input array as a pre-sorted subarray. Starting from the second element, each value is compared against elements in the pre-sorted section and placed in its appropriate ordered position. It has an average and worst-case time complexity of O(n²).

void insertionSort(int inputArr[], int arrLen) {
    for (int currIdx = 1; currIdx < arrLen; currIdx++) {
        int currentVal = inputArr[currIdx];
        int prevIdx = currIdx - 1;
        while (prevIdx >= 0 && currentVal < inputArr[prevIdx]) {
            inputArr[prevIdx + 1] = inputArr[prevIdx];
            prevIdx--;
        }
        inputArr[prevIdx + 1] = currentVal;
    }
}

Quick Sort

Core logic:

1. Select a pivot value, which can be the first, last, middle or a random element of the current segment
2. Partition the current segment so all elements smaller than the pivot are placed to its left, and all larger elements to the right
3. Recursively run the same process on the left and right partitions

Partitioning process:

• Initialize a left pointer at the start of the segment, which moves right as long as it points to a value smaller than the pivot
• Initialize a right pointer at the end of the segment, which moves left as long as it points to a value larger than the pivot
• When both pointers stop and have not crossed eachother, swap the values the two pointers reference, then repeat until the pointers cross

void quickSort(int q[], int left, int right) {
    if (left >= right) return;
    int i = left - 1, j = right + 1;
    int pivot = q[left + (right - left) / 2];
    while (i < j) {
        do i++; while (q[i] < pivot);
        do j--; while (q[j] > pivot);
        if (i < j) swap(q[i], q[j]);
    }
    quickSort(q, left, j);
    quickSort(q, j + 1, right);
}

Merge Sort

Core logic:

1. Split the current array segment at its midpoint to get two sub-segments
2. Recursively sort both left and right sub-segments
3. Merge the two sorted sub-segments into a single ordered segment (this is the core step of the algorithm)

Merging process:

• Use two pointers to traverse the sorted left and right sub-segments respectively
• Compare the values referenced by the two pointers, add the smaller value to a temporary auxiliary array
• After one sub-segment is fully traversed, append all remaining elements from the other sub-segment to the auxiliary array
• Copy the values from the auxiliary array back to the original input array

// Assume tempArr is a pre-allocated auxiliary array with sufficient size
void mergeSort(int q[], int left, int right, int tempArr[]) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(q, left, mid, tempArr);
    mergeSort(q, mid + 1, right, tempArr);
    int tempIdx = 0, leftPtr = left, rightPtr = mid + 1;
    while (leftPtr <= mid && rightPtr <= right) {
        if (q[leftPtr] <= q[rightPtr]) {
            tempArr[tempIdx++] = q[leftPtr++];
        } else {
            tempArr[tempIdx++] = q[rightPtr++];
        }
    }
    while (leftPtr <= mid) tempArr[tempIdx++] = q[leftPtr++];
    while (rightPtr <= right) tempArr[tempIdx++] = q[rightPtr++];
    for (int i = left, j = 0; i <= right; i++, j++) {
        q[i] = tempArr[j];
    }
}

Bubble Sort

This algorithm works by repeatedly comparing adjacent element pairs, swapping their positions if they are in reverse order. A total of n-1 full passes are required for an array of length n, with each subsequent pass requiring one fewer comparison than the last, as the largest unsorted element "bubbles up" to its correct position at the end of the array in each pass.

void bubbleSort(int arr[], int arrLength) {
    for (int pass = 0; pass < arrLength - 1; pass++) {
        bool swapped = false;
        for (int idx = 0; idx < arrLength - pass - 1; idx++) {
            if (arr[idx] > arr[idx + 1]) {
                int temp = arr[idx];
                arr[idx] = arr[idx + 1];
                arr[idx + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break; // Early exit if no swaps occur (array already sorted)
    }
}