Problem Definition

Given an array of stock prices representing daily records, an inversion pair is defined as a tuple $(i, j)$ where $i < j$ and $record[i] > record[j]$. The objective is to calculate the total count of such pairs within the input array. For instance, given the input [9, 7, 5, 4, 6], the inversion pairs are (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), and (5, 4), resulting in a total of 8.

Divide and Conquer Strategy

A brute force approach checking every pair would result in $O(N^2)$ time complexity, which is inefficient for large datasets. Instead, we can utilize the Merge Sort algorithm, which naturally fits the divide and conquer paradigm. The key insight is that during the merge phase, when two sorted sub-arrays are combined, we can efficiently detect inversion pairs.

When merging the left and right sub-arrays, we maintain two pointers. If the element at the current left pointer is less than or equal to the element at the current right pointer, no new inversions are introduced relative to the left element. However, if the left element is greater than the right element, it implies that all remaining elements in the left sub-array are also greater than the current right element (since the sub-arrays are sorted). Consequently, the number of inversions increases by the number of remaining elements in the left sub-array.

Implementation

The following Java solution implements this logic. It recursively splits the array and calculates the inversion count during the merging process.

class Solution {
    private int globalInversionCount = 0;
    private int[] tempBuffer;

    public int reversePairs(int[] data) {
        if (data == null || data.length == 0) {
            return 0;
        }
        tempBuffer = new int[data.length];
        executeMergeSort(data, 0, data.length - 1);
        return globalInversionCount;
    }

    private void executeMergeSort(int[] data, int startIdx, int endIdx) {
        if (startIdx >= endIdx) {
            return;
        }
        int midPoint = startIdx + (endIdx - startIdx) / 2;
        executeMergeSort(data, startIdx, midPoint);
        executeMergeSort(data, midPoint + 1, endIdx);
        mergeSortedHalves(data, startIdx, midPoint, endIdx);
    }

    private void mergeSortedHalves(int[] data, int startIdx, int midPoint, int endIdx) {
        // Copy current segment to auxiliary buffer
        System.arraycopy(data, startIdx, tempBuffer, startIdx, endIdx - startIdx + 1);

        int left = startIdx;
        int right = midPoint + 1;
        int current = startIdx;

        while (left <= midPoint && right <= endIdx) {
            if (tempBuffer[left] <= tempBuffer[right]) {
                data[current++] = tempBuffer[left++];
            } else {
                // An inversion is found. Since the left side is sorted,
                // all elements after 'left' are greater than tempBuffer[right].
                globalInversionCount += (midPoint - left + 1);
                data[current++] = tempBuffer[right++];
            }
        }

        // Copy remaining elements from the left side
        while (left <= midPoint) {
            data[current++] = tempBuffer[left++];
        }
        // No need to copy remaining right elements as they are already in place
    }
}

Complexity Analysis

The time complexity of this approach is O(N log N) because the array is divided in half at each step (log N levels) and the merging process takes linear time (N) at each level. The space complexity is O(N) due to the auxiliary array required to store temporary data during the merge phase.