Question

JAVA

Provide a simple code sample of Merge sort

Answer 1

//MergeSortRandomArray.java
import java.util.Random;
public class MergeSortRandomArray {
    public 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);
        }
    }

    public static void merge(int arr[], int left, int mid, int right)
    {
        int size1 = mid - left + 1;
        int size2 = right - mid;

        int leftArr[] = new int [size1];
        int rightArr[] = new int [size2];

        for (int i=0; i<size1; ++i)
            leftArr[i] = arr[left + i];
        for (int j=0; j<size2; ++j)
            rightArr[j] = arr[mid + 1+ j];


        int i = 0, j = 0;

        int k = left;
        while (i < size1 && j < size2)
        {
            if (leftArr[i] <= rightArr[j])
            {
                arr[k] = leftArr[i];
                i++;
            }
            else
            {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        while (i < size1)
        {
            arr[k] = leftArr[i];
            i++;
            k++;
        }

        while (j < size2)
        {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    public static void main(String args[]){
        int arr[] = new int[5];
        Random rand = new Random();
        System.out.println("Random array: ");
        for(int i = 0;i<arr.length;i++){
            arr[i] = 1+rand.nextInt(100);
            System.out.print(arr[i]+" ");
        }
        MergeSort(arr,0,arr.length-1);
        System.out.println("\n\nSorted array: ");
        for(int i = 0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
}