Mergesort
/*
This is pretty much taken word for word.
*/
//g++-12 -std=c++17 -o mergesort.out mergesort.cpp && ./mergesort.out
#include <iostream>
#include <random>
#include <time.h>
using std::mt19937,
std::cerr;
void merge(int nums[], int const left, int const mid, int const right)
{
int const subArrayOne = mid - left + 1;
int const subArrayTwo = right - mid;
int *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];
for (int i = 0; i < subArrayOne; i++)
leftArray[i] = nums[left + i];
for (int j = 0; j < subArrayTwo; j++)
rightArray[j] = nums[mid + 1 + j];
int indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;
int indexOfMergedArray = left;
while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {
if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
nums[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else {
nums[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}
while (indexOfSubArrayOne < subArrayOne) {
nums[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}
while (indexOfSubArrayTwo < subArrayTwo) {
nums[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
delete[] leftArray;
delete[] rightArray;
}
void mergeSort(int nums[], int const begin, int const end)
{
if (begin >= end)
return;
int mid = begin + (end - begin) / 2;
mergeSort(nums, begin, mid);
mergeSort(nums, mid + 1, end);
merge(nums, begin, mid, end);
}
int main(){
mt19937 rnd(time(NULL));
const int size = 15;
int a[size];
for(int i = 0; i < size; ++i){
a[i] = rnd() % 49 + 1;
cerr << "a[" << i << "]: " << a[i];
if(i < (size - 1)){
cerr << ", ";
}
}
cerr << "\n";
mergeSort(a, 0, size - 1);
for(int i = 0; i < size; ++i){
cerr << "a[" << i << "]: " << a[i];
if(i < (size - 1)){
cerr << ", ";
}
}
cerr << "\n";
return 0;
}
home