#include <iostream>
#include <cstdlib> // For rand() and srand()
#include <ctime> // For clock() and time()
using namespace std;
// Merge function
void merge(int arr[], int left, int mid, int right) {
int i = left, j = mid + 1, k = 0;
int temp[right - left + 1];
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (i = left, k = 0; i <= right; i++, k++) {
arr[i] = temp[k];
}
}
// Merge Sort function
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2; // Using midpoint formula directly
cout << "Mid is " << mid << endl;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Function to generate random numbers in the array
void generateRandomArray(int arr[], int size) {
srand(time(0)); // Seed for random number generator
for (int i = 0; i < size; i++) {
arr[i] = rand() % 1000; // Random numbers between 0 to 999
}
}
int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int arr[n];
generateRandomArray(arr, n);
cout << "Original array: ";
printArray(arr, n);
// Time calculation starts
clock_t start = clock();
mergeSort(arr, 0, n - 1);
clock_t end = clock();
cout << "Sorted array: ";
printArray(arr, n);
double time_taken = double(end - start) * 1000.0 / CLOCKS_PER_SEC;
cout << "Time taken for sorting " << n << " elements: "
<< time_taken << " ms" << endl;
return 0;
}
