Merge Sort HW

28 Mar 2025 • Project Work

Merge sort is a sorting algorithm. It works by dividing the array repeatedly into half until all pieces are groups of 1 or 2. It then sorts all of these blocks, before merging arrays back up and sorting them together. It is different from selection and bubble sort which have a sorted block that they sort elements one by one into.

Time complexity can be divided into two sections, the splitting and the merging. The splitting takes n - 1 operations, since by the end each element ends up individually, so each element except one had to be split. Then, for each level, n operations must be done to compares objects to the ones beside them. This must be done for each of log2(n) splits, giving us O(n*log2n) for the merging. For large values of n, however, n-1 is negligible and therefore the time complexity is O(nlog2(n))

public class MergeSortInversions {
    public static int mergeSortAndCount(int[] arr) {
        int[] temp = new int[arr.length];
        return mergeSortAndCountHelper(arr, temp, 0, arr.length - 1);
    }

    private static int mergeSortAndCountHelper(int[] arr, int[] temp, int left, int right) {
        int inversionCount = 0;
        if (left < right) {
            int mid = (left + right) / 2;
            
            inversionCount += mergeSortAndCountHelper(arr, temp, left, mid);
            inversionCount += mergeSortAndCountHelper(arr, temp, mid + 1, right);
            inversionCount += mergeAndCount(arr, temp, left, mid, right);
        }
        return inversionCount;
    }

    private static int mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = left;
        int inversionCount = 0;

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

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

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

        System.arraycopy(temp, left, arr, left, right - left + 1);

        return inversionCount;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 8, 6, 1};
        System.out.println("Number of inversions: " + mergeSortAndCount(arr));
    }
}

MergeSortInversions.main(new String[]{})

Number of inversions: 5

float a = 1;
int b = 3;

System.out.println(a * b);
System.out.println(a / b);

3.0
0.33333334

Comments

You are seeing this because your Disqus shortname is not properly set. To configure Disqus, you should edit your _config.yml to include either a disqus.shortname variable.

If you do not wish to use Disqus, override the comments.html partial for this theme.

Related Posts