//Merge sort code reference: https://www.softwaretestinghelp.com/merge-sort/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int candies = 0;
void merge(vector<int> &vect,int, int , int );
void merge_sort(vector<int> &vect, 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(vect,low,mid);
merge_sort(vect,mid+1,high);
//merge or conquer sorted arrays
merge(vect,low,high,mid);
}
}
// Merge sort
void merge(vector<int> &vect, int low, int high, int mid)
{
int i, j, k, diff, best, worst;
vector<int>vect2;
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high) {
if (vect[i] < vect[j]) {
vect2.push_back(vect[i]);
k++;
i++;
}
else {
vect2.push_back(vect[j]);
k++;
j++;
}
}
while (i <= mid) {
vect2.push_back(vect[i]);
k++;
i++;
}
while (j <= high) {
vect2.push_back(vect[j]);
k++;
j++;
}
//vect.clear();
for (i = low; i < k; i++) {
vect.push_back(vect2[i]);
}
for(i = low; i < k; i++)
{
cout << vect[i] << " ";
}
//n = sizeof(arr) / sizeof(arr[low]);
worst = vect[low];
best = vect[high];
/*int *what;
f = arr[0];
what = std::max_element(arr, arr + k);
l = *what;*/
diff = best - worst;
candies = candies + diff;
cout << "diff: " << diff << endl;
}
// read input array and call mergesort
int main()
{
int num, entry;
vector<int> vect;
cin>>num;
for (int i = 0; i < num; i++) { cin>>entry;
vect.push_back(entry);
cout << vect[i] << " ";
}
cout << endl;
merge_sort(vect, 0, num-1);
cout << endl;
cout<<"Sorted array\n";
for (int i = 0; i < num; i++)
{
cout<<vect[i]<<"\t";
}
cout << "candy count: " << candies;
//cout << candies;
}
