We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Merge Sort: Counting Inversions
  2. Discussions

Merge Sort: Counting Inversions

  • vaisakhkolathara
     + 0 comments

    For people looking for PHP solution. You can use the merge sort procedure to solve this

    function countInversions($arr) {
    $temp = array_fill(0, count($arr), 0);
    return mergeSort($arr, $temp, 0, count($arr) - 1);
}

function mergeSort(&$arr, &$temp, $left, $right) {
    $inversions = 0;
    if ($left < $right) {
        $mid = (int)(($left + $right) / 2);
        $inversions += mergeSort($arr, $temp, $left, $mid);
        $inversions += mergeSort($arr, $temp, $mid + 1, $right);
        $inversions += merge($arr, $temp, $left, $mid, $right);
    }
    return $inversions;
}

function merge(&$arr, &$temp, $left, $mid, $right) {
    $i = $left;
    $j = $mid + 1;
    $k = $left;
    $inversions = 0;

    while ($i <= $mid && $j <= $right) {
        if ($arr[$i] <= $arr[$j]) {
            $temp[$k++] = $arr[$i++];
        } else {
            $temp[$k++] = $arr[$j++];
            // Count inversions
            $inversions += ($mid - $i + 1);
        }
    }

    while ($i <= $mid) {
        $temp[$k++] = $arr[$i++];
    }

    while ($j <= $right) {
        $temp[$k++] = $arr[$j++];
    }

    // Copy back the merged elements to the original array
    for ($i = $left; $i <= $right; $i++) {
        $arr[$i] = $temp[$i];
    }

    return $inversions;
}