/*
 * Name: Owen Sullivan
 * Date Submitted: 9/29/22
 * Lab Section: 006
 * Assignment Name: Lab 4: Searching and Sorting
 */

#ifndef SORTS_
#define SORTS_

#include <vector>
#include <cstdlib>
#include <algorithm>

// Helper function for mergeSort() that sorts and merges halves of split vector
template <class T>
std::vector<T> merge(std::vector<T> &firstHalf, std::vector<T> &secondHalf) {

    // Set position iterators for both halves to
    // compare against in while loop
    int firstHalfPos = 0;
    int secondHalfPos = 0;

    std::vector<T> sorted;

    // Loop until the last value in either half is reached
    while (firstHalfPos < firstHalf.size() && secondHalfPos < secondHalf.size()) {

        // If a value in firstHalf is less than the corresponding index value in
        // secondHalf
        if (firstHalf.at(firstHalfPos) < secondHalf.at(secondHalfPos)) {

            // Push value in firstHalf to sorted vector
            sorted.push_back(firstHalf.at(firstHalfPos));
            // Increment firstHalf index
            firstHalfPos++;

         // If a value in secondHalf is less than the corresponding index value in
         // firstHalf
        } else {

            // Push value in secondHalf to sorted vector
            sorted.push_back(secondHalf.at(secondHalfPos));
            // Incremenet secondHalf index
            secondHalfPos++;

        }

    }

    // Add any remaining values in firstHalf to end of sorted
    // vector
    for (int pos = firstHalfPos; pos < firstHalf.size(); pos++) {

        sorted.push_back(firstHalf.at(pos));

    }
    // Add any remaining values in secondHalf to end of sorted
    // vector
    for (int pos = secondHalfPos; pos < secondHalf.size(); pos++) {

        sorted.push_back(secondHalf.at(pos));

    }

    // Return sorted vector
    return sorted;

}

template <class T>
std::vector<T> mergeSort(std::vector<T> &lst) {
    
    // If the list has one element (meaning it's not sortable),
    // return list
    if (lst.size() == 1) {

        return lst;

    }

    std::vector<T> firstHalf;
    std::vector<T> secondHalf;

    // Add elements to left of middle index (inclusive) to firstHalf
    for (int pos = 0; pos < (lst.size() / 2); pos++) {

        firstHalf.push_back(lst.at(pos));

    }
    // Add elements to left of middle index (inclusive) to secondHalf
    for (int pos = (lst.size() / 2); pos < lst.size(); pos++) {

        secondHalf.push_back(lst.at(pos));

    }

    // Recursively call mergeSort() on both halves to split them
    // into smaller halves
    firstHalf = mergeSort(firstHalf);
    secondHalf = mergeSort(secondHalf);

    // Call helper function merge() to sort halves
    lst = merge(firstHalf, secondHalf);

    // Return list
    return lst;

}

template <class T>
std::vector<T> quickSort(std::vector<T> &lst) {

    int pivotIndex;
    
    // If the list has less than two elements (meaning it's not sortable),
    // return list
    if (lst.size() == 0 || lst.size() == 1) {

        return lst;

      // If the list has at least two elements (meaning it's sortable)
    } else {

        // Get random index in list
        pivotIndex = rand() % lst.size();

    }

    // Set pivotValue as the value at pivotIndex
    T pivotValue = lst.at(pivotIndex);

    // Swap pivotValue with the first value in list, then
    // set pivotIndex to 0
    std::iter_swap(lst.begin() + 0, lst.begin() + pivotIndex);
    pivotIndex = 0;

    // Loop through the rest of the vector starting with the
    // value after the pivot index
    for (int pos = pivotIndex; pos < lst.size(); pos++) {

        // If the value at pos is less than the pivotValue
        if (lst.at(pos) < pivotValue) {

            // Increment pivotIndex
            pivotIndex++;

            // Swap the value at pivotIndex with the value at pos
            std::iter_swap(lst.begin() + pos, lst.begin() + pivotIndex);

        }

    }

    // Swap pivotValue with the value at pivotIndex
    std::iter_swap(lst.begin() + 0, lst.begin() + pivotIndex);

    std::vector<T> firstHalf;
    std::vector<T> secondHalf;

    // Add elements to left of pivotIndex to firstHalf
    for (int pos = 0; pos < pivotIndex; pos++) {

        firstHalf.push_back(lst.at(pos));

    }
    // Add elements to right of pivotIndex to secondHalf
    for (int pos = (pivotIndex + 1); pos < lst.size(); pos++) {

        secondHalf.push_back(lst.at(pos));

    }

    // Recursively call quickSort() on both halves to sort them
    firstHalf = quickSort(firstHalf);
    secondHalf = quickSort(secondHalf);

    // Add sorted elements back to list on left side of pivotIndex (replacing
    // current values)
    for (int pos = 0, halfPos = 0; pos < pivotIndex; pos++, halfPos++) {

        lst.at(pos) = firstHalf.at(halfPos);

    }
    // Add sorted elements back to list on right side of pivotIndex (replacing
    // current values)
    for (int pos = (pivotIndex + 1), halfPos = 0; pos < lst.size(); pos++, halfPos++) {

        lst.at(pos) = secondHalf.at(halfPos);

    }

    // Return list
    return lst;

}

#endif