What is Merge Sort?

Merge sort is a divide-and-conquer method that sorts an array by splitting it into half recursively until the subarrays are of size 1 or 0, then merging them back together in sorted order. The main notion underlying this technique is that merging two sorted arrays is substantially easier than sorting an unsorted array.

Algorithm:

The merge sort algorithm can be implemented as follows:

1. Divide the unsorted array into two halves, left and right
2. Recursively sort the left and right halves
3. Merge the two sorted halves back together

Time Complexity:

• Worst case: O(n log(n))
• Best case: Ω(n log(n))
• Average case: Θ(n log(n))

Implementation of the algorithm in Java:

public static void mergeSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    int[] temp = new int[arr.length];
    mergeSortHelper(arr, temp, 0, arr.length - 1);
}

private static void mergeSortHelper(int[] arr, int[] temp, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSortHelper(arr, temp, left, mid);
        mergeSortHelper(arr, temp, mid + 1, right);
        merge(arr, temp, left, mid, right);
    }
}

private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
    for (int i = left; i <= right; i++) {
        temp[i] = arr[i];
    }
    int leftPointer = left;
    int rightPointer = mid + 1;
    int current = left;
    while (leftPointer <= mid && rightPointer <= right) {
        if (temp[leftPointer] <= temp[rightPointer]) {
            arr[current] = temp[leftPointer];
            leftPointer++;
        } else {
            arr[current] = temp[rightPointer];
            rightPointer++;
        }
        current++;
    }
    while (leftPointer <= mid) {
        arr[current] = temp[leftPointer];
        leftPointer++;
        current++;
    }
}

Problems based on Merge sort:

• You are given an array A consisting of N integers. A subsequence of the array is called good if every pair of elements in the subsequence have an absolute difference of at most 10. Determine the maximum possible length of good subsequence.

Example:

Assumptions
N = 8
A = [1, 9, 14, 2, 17, 14, 5, 18]
Approach
Subsequence: [9,14,17,14,18] is good which is the maximum length subsequence.
Hence the output is 5.

Solution:

import java.util.Arrays;

public class GoodSubsequence {
    
    public static void main(String[] args) {
        int[] A = {1, 9, 14, 2, 17, 14, 5, 18};
        int n = A.length;
        
        // sort the array using merge sort
        mergeSort(A, 0, n-1);
        
        // find the length of the longest good subsequence
        int maxLen = longestGoodSubsequence(A, n);
        
        System.out.println("Maximum length of good subsequence: " + maxLen);
    }
    
    // implementation of merge sort
    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid+1, right);
            merge(arr, left, mid, right);
        }
    }
    
    // implementation of merge operation in merge sort
    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        
        int[] L = new int[n1];
        int[] R = new int[n2];
        
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left+i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid+1+j];
        }
        
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    
    // implementation of finding the length of longest good subsequence
    private static int longestGoodSubsequence(int[] arr, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (Math.abs(arr[i]-arr[j]) <= 10) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        
        return maxLen;
    }
}

Note: also read about Quick Sort

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py