#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_ORDERS 1000000
long A[MAX_ORDERS]; // Single array to store timestamps
long temp[MAX_ORDERS]; // Temporary array for merge
// Merge two sorted halves
void merge(int left, int mid, int right) {
int i = left; // Start of left half
int j = mid + 1; // Start of right half
int k = left; // Index for temp array
while (i <= mid && j <= right) {
if (A[i] <= A[j]) {
temp[k++] = A[i++];
} else {
temp[k++] = A[j++];
}
}
while (i <= mid) {
temp[k++] = A[i++];
}
while (j <= right) {
temp[k++] = A[j++];
}
// Copy back to original array
for (int l = left; l <= right; l++) {
A[l] = temp[l];
}
}
// Recursive merge sort function
void mergeSort(int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(left, mid);
mergeSort(mid + 1, right);
merge(left, mid, right);
}
}
// Generate random timestamps
void generateTimestamps(int n) {
for (int i = 0; i < n; i++) {
A[i] = rand() % 1000000000 + 1500000000; // Random UNIX-like timestamps
}
}
// Display first 10 timestamps
void displayTimestamps(int n) {
int limit = n < 10 ? n : 10;
for (int i = 0; i < limit; i++) {
printf("Timestamp[%d]: %ld\n", i, A[i]);
}
}
int main() {
int n = 1000000; // Number of timestamps (orders)
srand(time(NULL));
generateTimestamps(n);
printf("Before Sorting (First 10 Timestamps):\n");
displayTimestamps(n);
clock_t start = clock();
mergeSort(0, n - 1);
clock_t end = clock();
printf("\nAfter Sorting (First 10 Timestamps):\n");
displayTimestamps(n);
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nTime taken to sort %d timestamps: %.4f seconds\n", n, time_taken);
return 0;
}