Question

Write A JAVA mergesort method that mergesorts array elements in descending order.

Write A JAVA binary search method that searches x in a sorted array with n elements and returns

its position if exist, -1 otherwise.

Answer 1

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 int binarySearch(int[] array, int num) {
    int low = 0;
    int high = array.length - 1;
    int mid;

    while (high >= low) {
        mid = (low + high) / 2;
        if (num < array[mid])
            high = mid - 1;
        else
        if (num == array[mid])
            return mid;
        else
            low = mid + 1;
    }
    return - 1;
}