template<typename T, typename C> void sort(vector<T> &array, C &comp) {
    vector<T> blank(array.size(), 0);
    mergeSort(array, blank, 0, array.size() - 1, comp);
}

#include "array.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct Compare {
    bool operator()(const string &first, const string &sec) {
      return first.size() < sec.size();
    }  
};
int main() {
    vector<string> str = {"aa", "a", "aaa"};
    Compare comp;
    vec::sort(str, comp);
    
    return 0;
}

#pragma once
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <ctime>
#include <cstdlib>
using namespace std;
/*
* Provides many algorithms and functions used with std::vector's
* @author M. Farnsworth
*/
namespace vec {
    /*
    * Sorts an std::vector either ascending or descending depending on ltog (least to greatest).
    * If ltog is false it sorts the std::vector in descending.
    * Is a proxy function between the user and the actuall sorting function.
    * Implements the merge sort algorithm.
    */
    template<typename T> void sort(vector<T> &array, bool ltog = true);
    /*
    * Sorts an std::vector based on the 'comp' given to it.
    * Is a proxy function between the user and the actuall sorting function.
    * Implements the merge sort algorithm.
    * Overloads the first 'sort'.
    */
    template<typename T, typename C> void sort(vector<T> &array, C &comp);
    
    /*
    * Second function in merge sort.
    * Can be called by user directly, they will just need to provide values for the rest of the parameters.
    * Don't call this function, call arr::sort(vector<int> &array, bool ltog) to sort.
    */
    template<typename T, typename C> void mergeSort(vector<T> &array, vector<T> &blank, int bottom, int top, C &comp);
    
    /*
    * Third function in merge sort.
    * Shouldn't be called by the user.
    */
    template<typename T, typename C> void merge(vector<T> &array, vector<T> &copy, int bottom, int half, int top, C &comp);
    
    /*
    * Swaps items at the indices 'first' and 'second' of the given std::vector.
    */
    template<typename T> void swap(vector<T> &array, int first, int second);
    /*
    * Reverses the order of the items in an std::vector.
    */
    template<typename T> void reverse(vector<T> &array);
    /*
    * Writes the items in an std::vector to an std::ostream.
    * Essentially this means it will display the array.
    * If called with only the std::vector it will display to the console or 'cout' by default.
    */
    template<typename T> void display(vector<T> &array, string diliminator = " ", bool endline = true, ostream &out = cout);
    /*
    * Provides a structor for comparing two T.
    * operator() returns true if first is less than second.
    * operator() returns false if first is greater or equal to second.
    * Used in 'merge' to sort an std::vector in ascending order.
    */
    template<typename T> struct SortLess;
    /*
    * Provides a structor for comparing two T.
    * operator() returns false if first is less than second.
    * operator() returns true if first is greater or equal to second.
    * Used in 'merge' to sort an std::vector in descending order.
    */
    template<typename T> struct SortGreater;
    template<typename T> struct SortLess {
        bool operator()(T &first, T &second) {
            return first < second;
        }
    };
    template<typename T> struct SortGreater {
        bool operator()(T &first, T &second) {
            return first > second;
        }
    };
    template<typename T> void sort(vector<T> &array, bool ltog) {
        vector<T> blank(array.size(), 0);
        if (ltog) {
            SortLess<T> comp;
            mergeSort(array, blank, 0, array.size() - 1, comp);
        } else {
            SortGreater<T> comp;
            mergeSort(array, blank, 0, array.size() - 1, comp);
        }
    }
    template<typename T, typename C> void sort(vector<T> &array, C &comp) {
        vector<T> blank(array.size(), 0);
        mergeSort(array, blank, 0, array.size() - 1, comp);
    }
    template<typename T, typename C> void mergeSort(vector<T> &array, vector<T> &blank, int bottom, int top, C &comp) {
        if (top != bottom) {
            int half = bottom + (top - bottom) / 2;
            mergeSort(array, blank, bottom, half, comp);
            mergeSort(array, blank, half + 1, top, comp);
            merge(array, blank, bottom, half, top, comp);
        }
    }
    template<typename T, typename C> void merge(vector<T> &array, vector<T> &copy, int bottom, int half, int top, C &comp) {
        for (int i = 0; i < array.size(); i++) {
            copy[i] = array[i];
        }
        
        int firstCount = bottom;
        int secCount = half + 1;
        int count = firstCount;
        
        while (firstCount <= half && secCount <= top) {
            if (comp(copy[firstCount], copy[secCount])) {
                array[count] = copy[firstCount];
                firstCount++;
            } else {
                array[count] = copy[secCount];
                secCount++;
            }
            count++;
        }
        
        for (int i = firstCount; i <= half; i++) {
            array[count] = copy[i];
            count++;
        }
        
        for (int i = secCount; i <= top; i++) {
            array[count] = copy[i];
            count++;
        }
    }
    template<typename T> void swap(vector<T> &array, int first, int second) {
        int temp = array[first];
        array[first] = array[second];
        array[second] = temp;
    }
    template<typename T> void reverse(vector<T> &array) {
        int len = array.size();
        for (int i = 0; i < ceil(len / 2.0); i++) {
            swap(array, i, len - 1 - i);
        }
    }
    template<typename T> void display(vector<T> &array, string diliminator, bool endline, ostream &out) {
        for (int i = 0; i < array.size(); i++) {
            out << array[i] << diliminator;
        }
        if (endline) out << endl;
    }
    
    template<typename T> void shuffle(vector<T> &array) {
        srand(time(0));
        for (int i = 0; i < array.size(); i++) {
            int k = rand() % (i + 1);
            swap(array, i, k);
        }
    }
};

vector<T> blank(array.size(), 0);

constexpr std::string(const char* s, const Allocator& alloc = Allocator() );

vector<T> blank(array.size());