// C++ program for Merge Sort
#include <bits/stdc++.h>
#include <fstream>
#include <string>
using namespace std;
// file reading
void fileupload(int arr[], string filename, int len) {
ifstream is(filename);
int cnt = 0;
int x;
while (cnt < arr[len] && is >> x)
arr[cnt++] = x;
is.close();
}
void merge(int array[], int const left, int const mid, int const right) {
int const subArrayOne = mid - left + 1;
int const subArrayTwo = right - mid;
auto *leftArray = new int[subArrayOne], *rightArray = new int[subArrayTwo];
for (auto i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];
auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;
int indexOfMergedArray = left;
while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {
if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
} else {
array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}
while (indexOfSubArrayOne < subArrayOne) {
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}
while (indexOfSubArrayTwo < subArrayTwo) {
array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
delete[] leftArray;
delete[] rightArray;
}
void mergeSort(int array[], int const begin, int const end) {
if (begin >= end)
return;
int mid = begin + (end - begin) / 2;
mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}
void printArray(int A[], int size) {
for (int i = 0; i < size; i++)
cout << A[i] << " ";
cout << endl;
}
int main() {
int len = 10000;
int arr[10000];
string filename = "data1.txt";
fileupload(arr, filename, len);
clock_t start, stop;
double totalTime;
start = clock();
mergeSort(arr, 0, len - 1);
stop = clock();
totalTime = (stop - start) / (double)CLOCKS_PER_SEC;
cout << "total time with -i :" << totalTime << endl;