//Merge sort code reference: https://www.softwaretestinghelp.com/merge-sort/
#include <iostream>
#include <algorithm>
using namespace std;
int candies = 0;
void merge(int *,int, int , int );
void merge_sort(int *arr, int low, int high)
{
int mid;
if (low < high){
//divide the array at mid and sort independently using merge sort
mid=(low+high)/2;
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
//merge or conquer sorted arrays
merge(arr,low,high,mid);
}
}
// Merge sort
void merge(int *arr, int low, int high, int mid)
{
int i, j, k, c[50], n, f, l, diff;
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
c[k] = arr[i];
k++;
i++;
}
else {
c[k] = arr[j];
k++;
j++;
}
}
while (i <= mid) {
c[k] = arr[i];
k++;
i++;
}
while (j <= high) {
c[k] = arr[j];
k++;
j++;
}
for (i = low; i < k; i++) {
arr[i] = c[i];
}
for(i = low; i < k; i++)
{
cout << arr[i] << " ";
}
cout << endl;
n = sizeof(arr) / sizeof(arr[low]);
f = arr[0];
l = arr[n - 1];
/*int *what;
f = arr[0];
what = std::max_element(arr, arr + k);
l = *what;*/
diff = l - f;
candies = candies + diff;
cout << "diff: " << diff << endl;
}
// read input array and call mergesort
int main()
{
int myarray[30], num;
cout<<"Enter number of elements to be sorted:";
cin>>num;
cout<<"Enter "<<num<<" elements to be sorted:";
for (int i = 0; i < num; i++) { cin>>myarray[i];
}
merge_sort(myarray, 0, num-1);
cout<<"Sorted array\n";
for (int i = 0; i < num; i++)
{
cout<<myarray[i]<<"\t";
}
cout << "candy count: " << candies;
}
