sort.hpp

#include <vector>

void mergeSort(std::vector<int>& array);
void mergeSortHelper(std::vector<int>& mainArray, std::vector<int>& auxiliaryArray, size_t startIdx, size_t endIdx);
void doMerge(std::vector<int>& mainArray, std::vector<int>& auxiliaryArray, size_t startIdx, size_t middleIdx, size_t endIdx);

void quickSort(std::vector<int>& array);
void quickSortHelper(std::vector<int>& array, std::vector<int>::iterator startIdx, std::vector<int>::iterator endIdx);
std::vector<int>::iterator paritition(std::vector<int>& array, std::vector<int>::iterator startIdx, std::vector<int>::iterator endIdx);

void heapSort(std::vector<int>& array);
void heapify(std::vector<int>& array);
void siftDown(std::vector<int>& heap, int currentIdx, int endIdx);





void mergeSort(std::vector<int>& array) {
    if(array.size() <= 1) {
        return;
    }
    std::vector<int> auxiliaryArray = array;
    mergeSortHelper(array, auxiliaryArray, 0, array.size() - 1);
}

void mergeSortHelper(std::vector<int>& mainArray, std::vector<int>& auxiliaryArray, size_t startIdx, size_t endIdx) {
    if(startIdx == endIdx) {
        return;
    }
    size_t middleIdx = (startIdx + endIdx) / 2;
    mergeSortHelper(auxiliaryArray, mainArray, startIdx, middleIdx);
    mergeSortHelper(auxiliaryArray, mainArray, middleIdx + 1, endIdx);
    doMerge(mainArray, auxiliaryArray, startIdx, middleIdx, endIdx);
}

void doMerge(std::vector<int>& mainArray, std::vector<int>& auxiliaryArray, size_t startIdx, size_t middleIdx, size_t endIdx) {
    size_t k = startIdx, i = startIdx, j = middleIdx + 1;

    while(i <= middleIdx && j <= endIdx) 
        if(auxiliaryArray[i] <= auxiliaryArray[j])
            mainArray[k++] = auxiliaryArray[i++];
        else
            mainArray[k++] = auxiliaryArray[j++];

    while(i <= middleIdx)
        mainArray[k++] = auxiliaryArray[i++];

    while(j <= endIdx)
        mainArray[k++] = auxiliaryArray[j++];
}

void quickSort(std::vector<int>& array) {
    quickSortHelper(array, array.begin(), array.end() - 1);
}

void quickSortHelper(std::vector<int>& array, std::vector<int>::iterator startIdx, std::vector<int>::iterator endIdx) {
    if(startIdx >= endIdx) {
        return;
    }
    auto pivotIdx = paritition(array, startIdx, endIdx);
    bool leftSubarrayIsSmaller = (pivotIdx - startIdx) < (endIdx - pivotIdx);
    if(leftSubarrayIsSmaller) {
        quickSortHelper(array, startIdx, pivotIdx - 1);
        quickSortHelper(array, pivotIdx + 1, endIdx);
    }
    else {
        quickSortHelper(array, pivotIdx + 1, endIdx);
        quickSortHelper(array, startIdx, pivotIdx - 1);
    }
}

std::vector<int>::iterator paritition(std::vector<int>& array, std::vector<int>::iterator startIdx, std::vector<int>::iterator endIdx) {
    int pivot = *startIdx;
    auto leftIdx = startIdx;
    auto rightIdx = endIdx;
    while(leftIdx < rightIdx) {
        while(leftIdx < rightIdx && *rightIdx >= pivot) --rightIdx;
        *leftIdx = *rightIdx;
        while(leftIdx < rightIdx && *leftIdx <= pivot) ++leftIdx;
        *rightIdx = *leftIdx;
    }
    *leftIdx = pivot;
    return leftIdx;
}

void heapSort(std::vector<int>& array) {
    int endIdx;
    heapify(array);
    for(endIdx = (int)array.size() - 1; endIdx > 0; --endIdx) {
        std::swap(array[0], array[endIdx]);
        siftDown(array, 0, endIdx - 1);
    }
}

void heapify(std::vector<int>& array) {
    int firstParentIdx = (int)(array.size() - 2) / 2, currentIdx;
    for(currentIdx = firstParentIdx; currentIdx >= 0; --currentIdx) {
        siftDown(array, currentIdx, (int)array.size() - 1);
    }
}

void siftDown(std::vector<int>& heap, int currentIdx, int endIdx) {
    int childOneIdx = currentIdx * 2 + 1, childTwoIdx, idxToSwap;
    while(childOneIdx <= endIdx) {
        childTwoIdx = (currentIdx * 2 + 2) <= endIdx ? (currentIdx * 2 + 2) : -1;
        idxToSwap = childOneIdx;

        if(childTwoIdx != -1 && heap[childTwoIdx] > heap[childOneIdx])
            idxToSwap = childTwoIdx;

        if(heap[idxToSwap] <= heap[currentIdx]) return;

        std::swap(heap[idxToSwap], heap[currentIdx]);
        currentIdx = idxToSwap;
        childOneIdx = currentIdx * 2 + 1;
    }
}