1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
|
void mergeSplit (short* array, short startP, short endP);
void merge (short* arr,short sP, short mP, short eP);
void mergeSort (short* arr, short size)
{
mergeSplit (arr,0,(size-1));
}
void mergeSplit (short* array, short startP, short endP)
{
if (startP < endP)
{
short midP = (startP + endP) / 2;
mergeSplit (array, startP, midP);
mergeSplit (array, (midP+1), endP);
merge(array, startP, midP, endP);
}
}
void merge (short* arr,short sP, short mP, short eP)
{
short leftIter = sP;
short rightIter = mP+1;
short tempIter = 0;
short tempSize = (eP -sP)+1;
short* tempArr = new short[tempSize];
while ((leftIter <= mP) && (rightIter <= eP))
{
if (arr[leftIter] <= arr[rightIter])
{
tempArr[tempIter] = arr[leftIter];
++tempIter;
++leftIter;
}
else
{
tempArr[tempIter] = arr[rightIter];
++tempIter;
++rightIter;
}
if (leftIter > mP)
{
for (; rightIter <= eP; ++rightIter, ++tempIter)
tempArr[tempIter] = arr[rightIter];
}
else
{
for (; leftIter <= mP; ++leftIter, ++tempIter)
tempArr[tempIter] = arr[leftIter];
}
}
for (short i=0, j=sP; j<=eP; ++i, ++j) arr[j] = tempArr[i];
delete[] tempArr;
}
|