基于归并排序计算十万整数逆序数的代码问题求助

Hey there! Let’s tackle these two issues one by one—they’re common pitfalls with file I/O and merge sort inversion count implementations, so we’ll get this sorted out (pun intended 😊).

This usually boils down to how you’re writing the sorted data to the file. Here are the most likely fixes:

• Wait until sorting is fully done before writing: If you’re writing to the file mid-recursion (e.g., inside your merge function), you’ll end up with out-of-order chunks because recursive calls process subarrays independently. Instead, wait until the entire array is sorted, then loop through the final sorted array and write each element to the file in order.
• Use the correct file write mode: If you’re using FileWriter without specifying the append flag, double-check you’re overwriting the file instead of appending. Use new FileWriter("output.txt", false) explicitly to start with a blank file (no leftover data from previous runs).
• Ensure your output stream is flushed/closed: Always close your writer (or use try-with-resources to handle this automatically) to make sure all buffered data gets written to the file. Forgetting to close the stream can leave partial data stuck in memory.

Example of safe file writing:

// After sorting is COMPLETED:
try (BufferedWriter writer = new BufferedWriter(new FileWriter("sorted_output.txt"))) {
    for (int num : sortedArray) {
        writer.write(Integer.toString(num));
        writer.newLine(); // Match input format with newlines between numbers
    }
} catch (IOException e) {
    e.printStackTrace();
}

This is almost certainly a combination of integer overflow and a logic error in your inversion counting:

1. Fix the data type first: The expected count (~2.4 billion) is larger than the maximum value of a 32-bit int (~2.1 billion). If you’re using an int to store the inversion count, it will overflow and wrap around to a tiny incorrect number like 8096. Switch to a long (64-bit integer) for all inversion count variables.

2. Fix the merge step logic: When counting cross-subarray inversions, you need to count all remaining elements in the left subarray when a right element is smaller. A common mistake is adding 1 instead of the number of remaining left elements. Here’s the corrected merge logic:

private static long mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
    int leftPtr = left;
    int rightPtr = mid + 1;
    int tempPtr = left;
    long inversionCount = 0;

    while (leftPtr <= mid && rightPtr <= right) {
        if (arr[leftPtr] <= arr[rightPtr]) {
            temp[tempPtr++] = arr[leftPtr++];
        } else {
            // All remaining elements in left subarray are > current right element
            temp[tempPtr++] = arr[rightPtr++];
            inversionCount += (mid - leftPtr + 1); // This is the key line!
        }
    }

    // Copy leftover elements from left/right subarrays to temp
    while (leftPtr <= mid) {
        temp[tempPtr++] = arr[leftPtr++];
    }
    while (rightPtr <= right) {
        temp[tempPtr++] = arr[rightPtr++];
    }

    // Copy sorted temp back to original array
    System.arraycopy(temp, left, arr, left, right - left + 1);

    return inversionCount;
}

private static long mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
    long totalInversions = 0;
    if (left < right) {
        int mid = left + (right - left) / 2; // Avoid overflow in mid calculation
        // Recursively count inversions in left and right subarrays
        totalInversions += mergeSortAndCount(arr, temp, left, mid);
        totalInversions += mergeSortAndCount(arr, temp, mid + 1, right);
        // Count cross-subarray inversions
        totalInversions += mergeAndCount(arr, temp, left, mid, right);
    }
    return totalInversions;
}

3. Verify input reading: Make sure you’re correctly reading all 100,000 integers from the input file. If you’re missing elements or reading malformed data, your inversion count will be wrong. Use BufferedReader to read each line and parse to int carefully.

Once you implement these fixes, both the sorted file output and inversion count should match your expectations.

内容的提问来源于stack exchange，提问作者Ram