Last active
April 2, 2019 03:59
-
-
Save switchswap/c9ab4fec22bc16c6f6cd470ede96d399 to your computer and use it in GitHub Desktop.
K-way Templated Merge Sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#ifndef MSORT_H | |
#define MSORT_H | |
#include <vector> | |
#include <utility> | |
template <class T, class Comparator> | |
void mergeSort(std::vector<T>& myArray, int k, Comparator comp) { | |
mergeHelper(myArray, k, comp, 0, (int)myArray.size()-1); | |
} | |
template <class T, class Comparator> | |
void mergeHelper(std::vector<T>& myArray, int k, Comparator comp, int first, int last) { | |
std::vector<std::pair<int, int>> indexes; //keep track of indexes | |
int partitionSize; | |
int remainder; | |
if (first < last) { | |
partitionSize = (last - first + 1) / k; //each parition has this many elements | |
remainder = (last - first + 1) % k; | |
int firstShift = 0; | |
//lastShift is based on first | |
int nextLast = first + firstShift; | |
for (unsigned int i = 0; i < k && i < last-first + 1; i++) { | |
int MPSize = partitionSize + [](int i, int rmdr) {if (i < rmdr) return 1; else return 0; }(i, remainder); //how much to increment | |
mergeHelper(myArray, k, comp, first + firstShift, nextLast + MPSize - 1); //recurr | |
indexes.push_back(std::pair<int, int>(first + firstShift, nextLast + MPSize - 1)); //add pair to index vector | |
firstShift += MPSize; | |
nextLast += MPSize; | |
} | |
merge(myArray, indexes, comp); | |
} | |
} | |
template <class T, class Comparator> | |
void merge(std::vector<T>& myArray, std::vector<std::pair<int, int>> indexes, Comparator comp) { | |
int mergeCount = 0; | |
std::pair<int, int> currSortedIndex = indexes.at(0); | |
while (mergeCount < indexes.size()-1) { | |
std::pair<int, int> currIndex = indexes.at(mergeCount + 1); | |
//merge here | |
std::vector<T> tempArray; | |
int leftStart = currSortedIndex.first; | |
int leftEnd = currSortedIndex.second; | |
int rightStart = currIndex.first; | |
int rightEnd = currIndex.second; | |
while (leftStart <= leftEnd || rightStart <= rightEnd) { | |
if (leftStart <= leftEnd && (rightStart > rightEnd || comp(myArray.at(leftStart), myArray.at(rightStart)))) { | |
//Push from left side | |
tempArray.push_back(myArray.at(leftStart)); | |
leftStart++; | |
} | |
else { | |
//Push from right side | |
tempArray.push_back(myArray.at(rightStart)); | |
rightStart++; | |
} | |
} | |
//Copy over sorted portion (2 indexes since this should copy at only the edited bounds but the temp array starts at 0) | |
for (size_t i = 0, j = currSortedIndex.first; i < tempArray.size() && j <= currIndex.second; i++, j++) { | |
myArray.at(j) = tempArray.at(i); | |
} | |
currSortedIndex.second = currIndex.second; | |
mergeCount++; | |
} | |
} | |
#endif |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment