Lakhasly

Question 2 Part (d): Comparison Report The crystal energy matching problem formally belongs to the category of bipartite matching under restricted cross-comparison oracles, an established computational challenge historically known as the Nuts and Bolts problem.The Divide and Conquer algorithm not only adheres rigorously to the cross-comparison constraints and achieves the theoretical optimal lower bound of O(n log n), but it also inherently organizes the matched pairs into ascending energy order.In contrast, the recursive Divide and Conquer implementation allocates temporary sub-lists during the partitioning phase, consuming O(n) auxiliary heap memory across any active recursion path, alongside O(log n) call stack frames in the average case and O(n) in the worst case.These physical boundaries invalidate standard non-comparison techniques like Hash Tables, Counting Sort, or Radix Sort, while also preventing the direct application of conventional single-array comparison sorting algorithms such as MergeSort, QuickSort, or HeapSort.In conclusion, although the Brute Force technique provides simplicity and minimal memory consumption for trivial inputs, it fails to scale and leaves output pairs unsorted.In sharp contrast, our Divide and Conquer algorithm implements a sophisticated dual-partitioning technique inspired by QuickSort.Subsequently, this newly discovered Earth match serves as an inverse pivot to partition the remaining Mars crystals into corresponding lower and higher energy subsets.By the Master Theorem, this achieves an optimal average time complexity of O(n log n), requiring only approximately 265,000 comparisons for 10,000 crystals--delivering an extraordinary performance improvement exceeding 180 times faster.In terms of memory consumption, Brute Force exhibits an advantage by operating purely iteratively with O(1) auxiliary space, requiring only a boolean tracking array or in-place flags.While this quadratic growth remains tolerable for negligible inputs like n = 4, it quickly becomes computationally prohibitive as the dataset expands

Question 2 Part (d): Comparison Report The crystal energy matching problem formally belongs to the category of bipartite matching under restricted cross-comparison oracles, an established computational challenge historically known as the Nuts and Bolts problem.The Divide and Conquer algorithm not only adheres rigorously to the cross-comparison constraints and achieves the theoretical optimal lower bound of O(n log n), but it also inherently organizes the matched pairs into ascending energy order.In contrast, the recursive Divide and Conquer implementation allocates temporary sub-lists during the partitioning phase, consuming O(n) auxiliary heap memory across any active recursion path, alongside O(log n) call stack frames in the average case and O(n) in the worst case.These physical boundaries invalidate standard non-comparison techniques like Hash Tables, Counting Sort, or Radix Sort, while also preventing the direct application of conventional single-array comparison sorting algorithms such as MergeSort, QuickSort, or HeapSort.In conclusion, although the Brute Force technique provides simplicity and minimal memory consumption for trivial inputs, it fails to scale and leaves output pairs unsorted.In sharp contrast, our Divide and Conquer algorithm implements a sophisticated dual-partitioning technique inspired by QuickSort.Subsequently, this newly discovered Earth match serves as an inverse pivot to partition the remaining Mars crystals into corresponding lower and higher energy subsets.By the Master Theorem, this achieves an optimal average time complexity of O(n log n), requiring only approximately 265,000 comparisons for 10,000 crystals--delivering an extraordinary performance improvement exceeding 180 times faster.In terms of memory consumption, Brute Force exhibits an advantage by operating purely iteratively with O(1) auxiliary space, requiring only a boolean tracking array or in-place flags.While this quadratic growth remains tolerable for negligible inputs like n = 4, it quickly becomes computationally prohibitive as the dataset expands