Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
mergeSort2 is an implementation of merge sort that uses O(n) extra space (copies the array exactly once) instead of O(nlog(n))
#include <iostream>
#include <vector>
#include <random>
using namespace std;
/* Returns whether a list is sorted */
bool isSorted(vector<int> & list);
/* Sorts a list using the standard merge sort algorithm everyone learns in school (requires O(nlog(n)) space) */
void mergeSort(vector<int> & list);
/* Sorts a list using an optimized version of the merge sort algorithm (makes only one copy of the list) */
void mergeSort2(vector<int> & list);
void mergeSort_sort(vector<int>::iterator sourceBegin,
vector<int>::iterator sourceEnd,
vector<int>::iterator destinationBegin,
vector<int>::iterator destinationEnd);
/* Merges the sorted elements from source1 and source2 into the destination */
void mergeSort_merge(vector<int> & source1, vector<int> & source2, vector<int> & destination);
/* Merges the sorted elements from source1 (from source1Begin to source1End)
* and source2 (from source2Begin to source2End) into the destination (destinationBegin - destinationEnd)
*/
void mergeSort_merge(vector<int>::iterator source1Begin,
vector<int>::iterator source1End,
vector<int>::iterator source2Begin,
vector<int>::iterator source2End,
vector<int>::iterator destinationBegin,
vector<int>::iterator destinationEnd);
/* Copies the source (from sourcePos to sourceLimit) into
* the destination (from destinationPos to destinationLimit)
*/
void copy(vector<int>::iterator sourcePos,
vector<int>::iterator sourceLimit,
vector<int>::iterator destinationPos,
vector<int>::iterator destinationLimit);
int main() {
/* System's random device */
random_device device;
/* One of C++11's good random number generators, seeded with the device */
mt19937 rng(device());
/* The random number distribution */
uniform_int_distribution<int> distribution(0, 0x7FFFFFFF);
vector<int> list(10000);
for (auto & num : list) {
/* Generates a random number within the distribution using the rng */
num = distribution(rng);
cout << num << endl;
}
cout << endl;
//mergeSort(list);
mergeSort2(list);
for (auto num : list) {
cout << num << endl;
}
cout << endl;
if (isSorted(list)) {
cout << "Sorted\n";
} else {
cout << "Not Sorted\n";
}
return 0;
}
bool isSorted(vector<int> & list) {
if (list.size() < 2) {
return true;
}
for (auto it = list.begin() + 1; it != list.end(); ++it) {
if(*(it - 1) > *it) {
return false;
}
}
return true;
}
void mergeSort(vector<int> & list) {
if (list.size() < 2) {
return;
}
vector<int> list1(list.begin(), list.begin() + list.size() / 2);
vector<int> list2(list.begin() + list.size() / 2, list.end());
mergeSort(list1);
mergeSort(list2);
mergeSort_merge(list1, list2, list);
}
void mergeSort2(vector<int> & list) {
if (list.size() < 2) {
return;
}
vector<int> source = list;
mergeSort_sort(source.begin(), source.end(), list.begin(), list.end());
}
void mergeSort_sort(vector<int>::iterator sourceBegin,
vector<int>::iterator sourceEnd,
vector<int>::iterator destinationBegin,
vector<int>::iterator destinationEnd) {
auto size = distance(sourceBegin, sourceEnd);
if (size < 2) {
return;
}
auto sourceMiddle = sourceBegin + size / 2;
auto destinationMiddle = destinationBegin + size / 2;
auto source1Begin = destinationBegin;
auto source1End = destinationMiddle;
auto source2Begin = destinationMiddle;
auto source2End = destinationEnd;
auto destination1Begin = sourceBegin;
auto destination1End = sourceMiddle;
auto destination2Begin = sourceMiddle;
auto destination2End = sourceEnd;
mergeSort_sort(source1Begin, source1End, destination1Begin, destination1End);
mergeSort_sort(source2Begin, source2End, destination2Begin, destination2End);
mergeSort_merge(destination1Begin, destination1End,
destination2Begin, destination2End,
destinationBegin, destinationEnd);
}
void mergeSort_merge(vector<int> & source1, vector<int> & source2, vector<int> & destination) {
mergeSort_merge(source1.begin(), source1.end(),
source2.begin(), source2.end(),
destination.begin(), destination.end());
}
void mergeSort_merge(vector<int>::iterator source1Begin,
vector<int>::iterator source1End,
vector<int>::iterator source2Begin,
vector<int>::iterator source2End,
vector<int>::iterator destinationBegin,
vector<int>::iterator destinationEnd) {
auto it1 = source1Begin;
auto it2 = source2Begin;
for (auto spot = destinationBegin; spot != destinationEnd; ++spot) {
if (it1 == source1End) {
copy(it2, source2End, spot, destinationEnd);
break;
} else if (it2 == source2End) {
copy(it1, source1End, spot, destinationEnd);
break;
} else if (*it1 < *it2) {
*spot = *it1;
++it1;
} else {
*spot = *it2;
++it2;
}
}
}
void copy(vector<int>::iterator sourcePos,
vector<int>::iterator sourceLimit,
vector<int>::iterator destinationPos,
vector<int>::iterator destinationLimit) {
while(sourcePos != sourceLimit && destinationPos != destinationLimit) {
*destinationPos = *sourcePos;
++sourcePos;
++destinationPos;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.