People holding numbered tickets stand in a queue in the order given by tickets. The organiser wants to know how disordered the queue is: count the pairs of positions i < j such that tickets[i] > tickets[j]. Write disorder(tickets) returning that count in O(n log n) time by sorting recursively and counting as you merge.
Examples
Input: tickets = [3, 1, 2]
Output: 2
Explanation: (3, 1) and (3, 2) are out of order.
Input: tickets = [1, 2, 3]
Output: 0
Constraints
0 <= len(tickets) <= 10**4, values may repeat; equal values are not out of order.- Recursion depth is about log2(n).
Goals
- Count cross pairs while merging two sorted halves
- Return both the sorted list and the count from each recursive call
- Recognise when a whole block of remaining left elements is out of order