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.

Time Complexity Analysis

• Merge Sort:

  • Best Case: O(n log n)

  • Average Case: O(n log n)

  • Worst Case: O(n log n)

  • Stable and efficient for large datasets.

• Comparison with Other Sorting Techniques:
  | Algorithm | Best Case | Average Case | Worst Case | Stable | Suitable for 1M+? |
  |------------------|-----------|--------------|------------|--------|-------------------|
  | Bubble Sort | O(n) | O(n²) | O(n²) | Yes | ❌ Too slow |
  | Selection Sort | O(n²) | O(n²) | O(n²) | No | ❌ Too slow |
  | Insertion Sort | O(n) | O(n²) | O(n²) | Yes | ❌ Too slow |
  | Merge Sort | O(n log n)| O(n log n) | O(n log n) | Yes | ✅ Very good |
  | Quick Sort | O(n log n)| O(n log n) | O(n²) | No | ✅ (with care) |

1. #include <stdio.h>

2. #include <stdlib.h>

3. #include <time.h>

4. 
   

5. // Merge function to combine two sorted halves

6. void merge(long arr[], long left, long mid, long right) {

7.     long n1 = mid - left + 1;

8.     long n2 = right - mid;

9. 
   

10.     // Temporary arrays

11.     long *L = (long *)malloc(n1 * sizeof(long));

12.     long *R = (long *)malloc(n2 * sizeof(long));

13. 
    

14.     for (long i = 0; i < n1; i++)

15.         L[i] = arr[left + i];

16.     for (long j = 0; j < n2; j++)

17.         R[j] = arr[mid + 1 + j];

18. 
    

19.     // Merge the temp arrays back into arr

20.     long i = 0, j = 0, k = left;

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

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

23.             arr[k++] = L[i++];

24.         else

25.             arr[k++] = R[j++];

26.     }

27. 
    

28.     // Copy remaining elements

29.     while (i < n1)

30.         arr[k++] = L[i++];

31.     while (j < n2)

32.         arr[k++] = R[j++];

33. 
    

34.     free(L);

35.     free(R);

36. }

37. 
    

38. // Recursive merge sort

39. void mergeSort(long arr[], long left, long right) {

40.     if (left < right) {

41.         long mid = left + (right - left) / 2;

42. 
    

43.         mergeSort(arr, left, mid);

44.         mergeSort(arr, mid + 1, right);

45. 
    

46.         merge(arr, left, mid, right);

47.     }

48. }

49. 
    

50. int main() {

51.     long n;

52.     printf("Enter number of customer orders: ");

53.     scanf("%ld", &n);

54. 
    

55.     if (n > 1000000) {

56.         printf("Error: Maximum 1,000,000 orders allowed.\n");

57.         return 1;

58.     }

59. 
    

60.     long *timestamps = (long *)malloc(n * sizeof(long));

61.     if (!timestamps) {

62.         printf("Memory allocation failed!\n");

63.         return 1;

64.     }

65. 
    

66.     printf("Enter timestamps (as integers):\n");

67.     for (long i = 0; i < n; i++) {

68.         scanf("%ld", &timestamps[i]);

69.     }

70. 
    

71.     clock_t start = clock();

72.     mergeSort(timestamps, 0, n - 1);

73.     clock_t end = clock();

74. 
    

75.     printf("\nSorted timestamps:\n");

76.     for (long i = 0; i < n; i++) {

77.         printf("%ld ", timestamps[i]);

78.     }

79. 
    

80.     double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;

81.     printf("\n\nMerge Sort completed in %.6f seconds.\n", time_taken);

82. 
    

83.     free(timestamps);

84.     return 0;

85. }

86. 
    

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.