Implementation of different sort algorithms.

sort.cpp

// --------------- Selection Sort---------------------//
void selectionSort(vector<int> &num) {
    int size = num.size();
    for(int i = 0; i < size ; i++) {
        int min = i;
        for(int j = i + 1; j < size; j++) {
            if(num[j] < num[min]) {
                min = j;
            }
        }
        swap(num[i], num[min]);
    }
}


// --------------- Quick Sort---------------------//
int partition(vector<int> &nums, int low, int high) {
    // equvalent to random pick up.
    swap(nums[low], nums[low + rand() % (high - low + 1)]);
    int pivot = nums[low];
    while(low < high) {
        while(low < high && pivot <= nums[high]) {
            high--;
        }
        nums[low] = nums[high];
        while(low < high && pivot >= nums[low]) {
            low++;
        }
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    return low;
}

void quickSort(vector<int> &nums, int low, int high) {
    if(high - low < 2) {
        return;
    }

    int idx = partition(nums, low, high);
    quickSort(nums, low, idx);
    quickSort(nums, idx + 1, high);
}


// --------------- Merge Sort---------------------//
void mergesort(vector<int> &arrays, int low, int high) {
    if (low < high) {
        int mid = low + (high-low)/2;
        mergesort(arrays, low, mid);
        mergesort(arrays, mid+1, high);
        merge(array, low, mid, high);
    }
}

void merge(vector<int> &array, int low, int mid, int high) {
    vector<int> helper(array.size());
    for(int i = low; i <= high; i++) {
        helper[i] = array[i];
    }
    int helperLeft = low;
    int helperRight = mid+1;
    int cur = low;
    while(helperLeft <= mid && helperRight <= right) {
        if (helper[helperLeft] <= helper[helperRight]) {
            array[cur] = helper[helperLeft];
            helperLeft++;
        } else {
            array[cur] = helper[helperRight];
            helperRight++;
        }
        cur++;
    }
    
    int remaining = mid - helperLeft;
    for(int i = 0; i <= remaining; i++) {
        array[cur+i] = helper[helperLeft+i];
    }
}