#include <iostream>
using namespace std;
//The merge function
void merge(int a[], int startIndex, int endIndex)
{
int size = (endIndex - startIndex) + 1;
int *b = new int [size]();
int i = startIndex;
int mid = (startIndex + endIndex)/2;
int k = 0;
int j = mid + 1;
while (k < size)
{
if((i<=mid) && (a[i] < a[j]))
{
b[k++] = a[i++];
}
else
{
b[k++] = a[j++];
}
}
for(k=0; k < size; k++)
{
a[startIndex+k] = b[k];
}
delete []b;
}
//The recursive merge sort function
void merge_sort(int iArray[], int startIndex, int endIndex)
{
int midIndex;
//Check for base case
if (startIndex >= endIndex)
{
return;
}
//First, divide in half
midIndex = (startIndex + endIndex)/2;
//First recursive call
merge_sort(iArray, startIndex, midIndex);
//Second recursive call
merge_sort(iArray, midIndex+1, endIndex);
//The merge function
merge(iArray, startIndex, endIndex);
}
//The main function
int main(int argc, char *argv[])
{
int iArray[10] = {2,5,6,4,7,2,8,3,9,10};
merge_sort(iArray, 0, 9);
//Print the sorted array
for(int i=0; i < 10; i++)
{
cout << iArray[i] << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy9UaGUgbWVyZ2UgZnVuY3Rpb24Kdm9pZCBtZXJnZShpbnQgYVtdLCBpbnQgc3RhcnRJbmRleCwgaW50IGVuZEluZGV4KQp7CgppbnQgc2l6ZSA9IChlbmRJbmRleCAtIHN0YXJ0SW5kZXgpICsgMTsKaW50ICpiID0gbmV3IGludCBbc2l6ZV0oKTsKCmludCBpID0gc3RhcnRJbmRleDsKaW50IG1pZCA9IChzdGFydEluZGV4ICsgZW5kSW5kZXgpLzI7CmludCBrID0gMDsKaW50IGogPSBtaWQgKyAxOwoKd2hpbGUgKGsgPCBzaXplKQp7ICAgCiAgICBpZigoaTw9bWlkKSAmJiAoYVtpXSA8IGFbal0pKQogICAgewogICAgICAgIGJbaysrXSA9IGFbaSsrXTsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBiW2srK10gPSBhW2orK107CiAgICB9Cgp9Cgpmb3Ioaz0wOyBrIDwgc2l6ZTsgaysrKQp7CiAgICBhW3N0YXJ0SW5kZXgra10gPSBiW2tdOwp9CgpkZWxldGUgW11iOwoKfQoKLy9UaGUgcmVjdXJzaXZlIG1lcmdlIHNvcnQgZnVuY3Rpb24Kdm9pZCBtZXJnZV9zb3J0KGludCBpQXJyYXlbXSwgaW50IHN0YXJ0SW5kZXgsIGludCBlbmRJbmRleCkKewppbnQgbWlkSW5kZXg7CgovL0NoZWNrIGZvciBiYXNlIGNhc2UKaWYgKHN0YXJ0SW5kZXggPj0gZW5kSW5kZXgpCnsKICAgIHJldHVybjsKfSAgIAoKLy9GaXJzdCwgZGl2aWRlIGluIGhhbGYKbWlkSW5kZXggPSAoc3RhcnRJbmRleCArIGVuZEluZGV4KS8yOwoKLy9GaXJzdCByZWN1cnNpdmUgY2FsbCAKbWVyZ2Vfc29ydChpQXJyYXksIHN0YXJ0SW5kZXgsIG1pZEluZGV4KTsKCi8vU2Vjb25kIHJlY3Vyc2l2ZSBjYWxsIAptZXJnZV9zb3J0KGlBcnJheSwgbWlkSW5kZXgrMSwgZW5kSW5kZXgpOwoKLy9UaGUgbWVyZ2UgZnVuY3Rpb24KbWVyZ2UoaUFycmF5LCBzdGFydEluZGV4LCBlbmRJbmRleCk7Cgp9CgovL1RoZSBtYWluIGZ1bmN0aW9uCmludCBtYWluKGludCBhcmdjLCBjaGFyICphcmd2W10pCnsKaW50IGlBcnJheVsxMF0gPSB7Miw1LDYsNCw3LDIsOCwzLDksMTB9OwoKbWVyZ2Vfc29ydChpQXJyYXksIDAsIDkpOwoKLy9QcmludCB0aGUgc29ydGVkIGFycmF5CmZvcihpbnQgaT0wOyBpIDwgMTA7IGkrKykKewogICAgY291dCA8PCBpQXJyYXlbaV0gPDwgZW5kbDsKfQoKcmV0dXJuIDA7ICAgIAp9