Steps: 

1. Ask the user for the number of orders.

2. Read timestamps (as integers).

3. Sort them using Merge Sort.

4. Analyze time complexity vs. other sorting algorithms.

 Merge Sort is preferred when stability and predictable performance are required (like customer orders). 

🔹 Time Complexity Analysis

• Best Case: O(nlog⁡n)O

• Average Case: O(nlog⁡n)

• Worst Case: O(nlog⁡n
  
  

where n = number of orders.

Memory usage: O(n)O(n)O(n) (extra space for merging).
Efficient for large datasets (like 1 million orders).

#include <bits/stdc++.h>

using namespace std;

// Structure to store customer order

struct Order {

    int id;

    long long timestamp; // Use long long for large timestamp values

};

// Merge function for Merge Sort

void merge(vector<Order>& orders, int left, int mid, int right) {

    int n1 = mid - left + 1;

    int n2 = right - mid;

    // Temp arrays

    vector<Order> L(n1), R(n2);

    for (int i = 0; i < n1; i++)

        L[i] = orders[left + i];

    for (int j = 0; j < n2; j++)

        R[j] = orders[mid + 1 + j];

    int i = 0, j = 0, k = left;

    // Merge the two halves

    while (i < n1 && j < n2) {

        if (L[i].timestamp <= R[j].timestamp) {

            orders[k] = L[i];

            i++;

        } else {

            orders[k] = R[j];

            j++;

        }

        k++;

    }

    // Copy remaining elements

    while (i < n1) {

        orders[k] = L[i];

        i++;

        k++;

    }

    while (j < n2) {

        orders[k] = R[j];

        j++;

        k++;

    }

}

// Recursive Merge Sort function

void mergeSort(vector<Order>& orders, int left, int right) {

    if (left < right) {

        int mid = left + (right - left) / 2;

        mergeSort(orders, left, mid);

        mergeSort(orders, mid + 1, right);

        merge(orders, left, mid, right);

    }

}

// Driver function

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n;

    cout << "Enter number of customer orders: ";

    cin >> n;

    vector<Order> orders(n);

    cout << "Enter order ID and timestamp:\n";

    for (int i = 0; i < n; i++) {

        cin >> orders[i].id >> orders[i].timestamp;

    }

    // Sort orders using Merge Sort

    mergeSort(orders, 0, n - 1);

    cout << "\nSorted Orders by Timestamp:\n";

    for (auto &o : orders) {

        cout << "Order ID: " << o.id << " | Timestamp: " << o.timestamp << "\n";

    }

    return 0;

}

Output:

Enter number of customer orders: 8

Enter timestamps (as integers):

202308121530

202307011200

202309101045

202301011230

202305051500

202304091000

202309101040

202302151430

Sorted timestamps:

202301011230 202302151430 202304091000 202305051500 202307011200 202308121530 202309101040 202309101045

Merge Sort completed in 0.000015 seconds.