#include <iostream>
using namespace std;
void printArray(int* arr, int len);
bool mSort(int *arr, int len);
void mergeArray(int *arr, int first, int mid, int last, int *temp);
void mergeSort(int *arr, int first, int last, int temp[]);
int main()
{
int arr[] = {1, 4, 3, 10, 4, 7, 2, 5};
int len = sizeof(arr)/sizeof(*arr);
printArray(arr, len);
mSort(arr, len);
printArray(arr, len);
cin.get();
return 0;
}
void mergeArray(int *arr, int first, int mid, int last, int *temp)
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while(i <= m && j <= n)
{
if(arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while(i <= m)
temp[k++] = arr[i++];
while(j <= n)
temp[k++] = arr[j++];
for(i = 0; i < k; i++)
arr[i + first] = temp[i];
}
void mergeSort(int *arr, int first, int last, int *temp)
{
if(first < last)
{
int mid = (first + last)/2;
mergeSort(arr, first, mid, temp);
mergeSort(arr, mid+1, last, temp);
mergeArray(arr, first, mid, last, temp);
}
}
bool mSort(int *arr, int len)
{
int *temp = new int[len];
if(temp == NULL)
return false;
mergeSort(arr, 0, len -1, temp);
delete[] temp;
return true;
}
void printArray(int* arr, int len)
{
for(int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
//cpp/8814