MergeSort alogorithm

Category : Data-structures-algorithms | Sub Category : MergeSort alogorithm | By Prasad Bonam Last updated: 2023-07-10 10:11:04 Viewed : 67

MergeSort alogorithm:

Here is an example of the MergeSort algorithm implemented in Java:

javaCopy code
public class MergeSort {
    
    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

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

    private static void merge(int[] arr, int left, int mid, int right) {
        int leftSize = mid - left + 1;
        int rightSize = right - mid;

        int[] leftArr = new int[leftSize];
        int[] rightArr = new int[rightSize];

        // Copy data to temporary arrays
        System.arraycopy(arr, left, leftArr, 0, leftSize);
        System.arraycopy(arr, mid + 1, rightArr, 0, rightSize);

        int i = 0, j = 0, k = left;

        // Merge the temporary arrays back into arr
        while (i < leftSize && j < rightSize) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        // Copy the remaining elements of leftArr, if any
        while (i < leftSize) {
            arr[k++] = leftArr[i++];
        }

        // Copy the remaining elements of rightArr, if any
        while (j < rightSize) {
            arr[k++] = rightArr[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = { 8, 5, 2, 9, 1, 6, 3, 7 };
        System.out.println("Original array: " + Arrays.toString(arr));
        
        mergeSort(arr);
        
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

In the mergeSort method, we define the base case where the left index is less than the right index. If the base case is satisfied, we calculate the middle index (mid) and recursively call mergeSort for the left and right halves of the array. Finally, we merge the two sorted halves using the merge method.

The merge method takes the left, middle, and right indices as parameters. It creates temporary arrays (leftArr and rightArr) to store the values of the left and right halves of the array. Then, it iterates over both halves, comparing the elements and merging them back into the original array in sorted order.

In the main method, we demonstrate the usage of the MergeSort algorithm by sorting an example array. The original array is printed before sorting, and the sorted array is printed afterward.

The MergeSort algorithm has a time complexity of O(n log n) and performs stable sorting.