#include <iostream>
#include <cstring>
using namespace std;
void mergeSort(int *array, int *temp, int leftStart, int rightEnd);
void mergeHalves(int *array, int *temp, int leftStart, int rightEnd);
void printArray(int* array, int size,string message){
cout<<message<<endl;
for (int i = 0; i < size; i++)
cout << *(array+i) << "\t";
cout << endl;
}
int main(){
const int size = 10;
int myInts[size] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
int temp[size] = {0};
printArray(myInts,size,"Input");
mergeSort(myInts, temp, 0, size-1);
printArray(myInts, size, "Output:");
return 0;
}
void mergeSort(int *array, int *temp, int leftStart, int rightEnd){
if (leftStart >= rightEnd)
return;
int middle = (leftStart + rightEnd) / 2;
mergeSort(array, temp, leftStart, middle);
mergeSort(array, temp, middle + 1, rightEnd);
mergeHalves(array,temp,leftStart,rightEnd);
return;
}
void mergeHalves(int *array, int *temp, int leftStart, int rightEnd){
int middle = (rightEnd + leftStart) / 2;
int size = rightEnd - leftStart + 1;
//cout << "Left: " << leftStart << ", Middle: " << middle << ", Right: " << rightEnd << endl;
int left = leftStart;
int right = middle + 1;
int index = leftStart;
while (left <= middle && right <= rightEnd){
if (array[left] <= array[right]){
temp[index] = array[left];
left++;
}else{
temp[index] = array[right];
right++;
}
index++;
}
memcpy(temp + index, array + left, (middle - left + 1) * sizeof(int));
memcpy(temp + index, array + right, (rightEnd - right + 1) * sizeof(int));
memcpy(array+leftStart, temp+leftStart, size * sizeof(int));
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgbWVyZ2VTb3J0KGludCAqYXJyYXksIGludCAqdGVtcCwgaW50IGxlZnRTdGFydCwgaW50IHJpZ2h0RW5kKTsKdm9pZCBtZXJnZUhhbHZlcyhpbnQgKmFycmF5LCBpbnQgKnRlbXAsIGludCBsZWZ0U3RhcnQsIGludCByaWdodEVuZCk7Cgp2b2lkIHByaW50QXJyYXkoaW50KiBhcnJheSwgaW50IHNpemUsc3RyaW5nIG1lc3NhZ2UpewogICAgY291dDw8bWVzc2FnZTw8ZW5kbDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrKQogICAgICAgIGNvdXQgPDwgKihhcnJheStpKSA8PCAiXHQiOwogICAgY291dCA8PCBlbmRsOwp9CmludCBtYWluKCl7CiAgICBjb25zdCBpbnQgc2l6ZSA9IDEwOwogICAgaW50IG15SW50c1tzaXplXSA9IHs5LCA4LCA3LCA2LCA1LCA0LCAzLCAyLCAxLCAwfTsKICAgIGludCB0ZW1wW3NpemVdID0gezB9OwogICAgcHJpbnRBcnJheShteUludHMsc2l6ZSwiSW5wdXQiKTsKICAgIG1lcmdlU29ydChteUludHMsIHRlbXAsIDAsIHNpemUtMSk7CiAgICBwcmludEFycmF5KG15SW50cywgc2l6ZSwgIk91dHB1dDoiKTsKCiAgICByZXR1cm4gMDsKfQoKdm9pZCBtZXJnZVNvcnQoaW50ICphcnJheSwgaW50ICp0ZW1wLCBpbnQgbGVmdFN0YXJ0LCBpbnQgcmlnaHRFbmQpewogICAgaWYgKGxlZnRTdGFydCA+PSByaWdodEVuZCkKICAgICAgICByZXR1cm47CgogICAgaW50IG1pZGRsZSA9IChsZWZ0U3RhcnQgKyByaWdodEVuZCkgLyAyOwoKICAgIG1lcmdlU29ydChhcnJheSwgdGVtcCwgbGVmdFN0YXJ0LCBtaWRkbGUpOwogICAgbWVyZ2VTb3J0KGFycmF5LCB0ZW1wLCBtaWRkbGUgKyAxLCByaWdodEVuZCk7CiAgICBtZXJnZUhhbHZlcyhhcnJheSx0ZW1wLGxlZnRTdGFydCxyaWdodEVuZCk7CiAgICByZXR1cm47Cn0KCnZvaWQgbWVyZ2VIYWx2ZXMoaW50ICphcnJheSwgaW50ICp0ZW1wLCBpbnQgbGVmdFN0YXJ0LCBpbnQgcmlnaHRFbmQpewogICAgaW50IG1pZGRsZSA9IChyaWdodEVuZCArIGxlZnRTdGFydCkgLyAyOwogICAgaW50IHNpemUgPSByaWdodEVuZCAtIGxlZnRTdGFydCArIDE7CiAgICAKICAgIC8vY291dCA8PCAiTGVmdDogIiA8PCBsZWZ0U3RhcnQgPDwgIiwgTWlkZGxlOiAiIDw8IG1pZGRsZSA8PCAiLCBSaWdodDogIiA8PCByaWdodEVuZCA8PCBlbmRsOwogICAgCiAgICBpbnQgbGVmdCA9IGxlZnRTdGFydDsKICAgIGludCByaWdodCA9IG1pZGRsZSArIDE7CiAgICBpbnQgaW5kZXggPSBsZWZ0U3RhcnQ7CgogICAgd2hpbGUgKGxlZnQgPD0gbWlkZGxlICYmIHJpZ2h0IDw9IHJpZ2h0RW5kKXsKICAgICAgICBpZiAoYXJyYXlbbGVmdF0gPD0gYXJyYXlbcmlnaHRdKXsKICAgICAgICAgICAgdGVtcFtpbmRleF0gPSBhcnJheVtsZWZ0XTsKICAgICAgICAgICAgbGVmdCsrOwogICAgICAgIH1lbHNlewogICAgICAgICAgICB0ZW1wW2luZGV4XSA9IGFycmF5W3JpZ2h0XTsKICAgICAgICAgICAgcmlnaHQrKzsKICAgICAgICB9CiAgICAgICAgaW5kZXgrKzsKICAgIH0KICAgIAogICAgCiAgICBtZW1jcHkodGVtcCArIGluZGV4LCBhcnJheSArIGxlZnQsIChtaWRkbGUgLSBsZWZ0ICsgMSkgKiBzaXplb2YoaW50KSk7CiAgICBtZW1jcHkodGVtcCArIGluZGV4LCBhcnJheSArIHJpZ2h0LCAocmlnaHRFbmQgLSByaWdodCArIDEpICogc2l6ZW9mKGludCkpOwogICAgbWVtY3B5KGFycmF5K2xlZnRTdGFydCwgdGVtcCtsZWZ0U3RhcnQsIHNpemUgKiBzaXplb2YoaW50KSk7CgkKfQ==