Merge Sort

Warm Up Exercises Prior to Coding Merge Sort

1. Write a static method called interleave that takes two arrays of integers and returns an array with the items from the two arrays interleaved. So if the first array contains [3, 9, 6, 5] and the second array contains [4, 5, 6, 1], the method would return a new array with the contents: [3, 4, 9, 5, 6, 6, 5, 1]. For this exercise, the two arrays are guaranteed to be of the same length.
   
   

2. Write a static method called interleaveInPlace that takes an array of integers (of even length) as its only parameter and modifies the array by interleaving items from the first half of the array with items from the second half.  So if the array parameter contains [3, 9, 6, 5, 2, 4] , the method would modify this array to contain [3, 5, 9, 2, 6, 4]. The method does not return anything. Hint: You will need to make copies of the two subarrays as part of the interleaving process.
   
   

3. Write a static method called interleave2 that takes two arrays of integers and returns an array with the items from the two arrays interleaved. So if the first array contains [3, 9, 7] and the second array contains [4, 5, 6, 1, 3, 6], the method would return a new array with the contents: [3, 4, 9, 5, 7, 6, 1, 3, 6]. For this exercise, the two arrays are NOT guaranteed to be of the same length. When one array is exhausted, remaining elements from the other array are appended to the solution.
   
   

4. Write a static method called mergeArrays that takes two sorted arrays as parameters and returns a sorted array consisting of the elements of the two arrays.  
   
   

5. Write a static method called interleaveInPlace2 that takes an array of integers and another integer as its only parameters and modifies the array by interleaving items from the first portion of the array with items from the second portion.  The position given by the second parameter specifies the dividing line in the array between the first and second portions. So if the array parameter contains [3, 9, 6, 5, 2, 4] , a call to the method like this ...
   
   interleaveInPlace2(array, 3);
   
   ... would signify that the first portion of the array is [3, 9, 6, 5] because the 3 in the second parameter marks the index of the last element in the first portion. The second portion of the array would be [2,4].  The method would modify this array to contain [3, 2, 9, 4, 6, 5]. The method does not return anything. Hint: You will need to make copies of the two subarrays as part of the interleaving process.

Merge Sort Project

Use the following algorithm and pseudocode to help you create your own merge sort code. (The pseudocode may be more helpful than the algorithm).

General Algorithm

step 1: start

step 2: declare array and left, right, mid variable

step 3: perform merge function.
    if left > right
        return
    mid= (left+right)/2
    mergesort(array, left, mid)
    mergesort(array, mid+1, right)

Pseudocode

class MergeSort {

/* A utility function to print array of size n */

    static void printArray(int arr[])

    {

       // you write this

    }

    // Merges two subarrays of arr[].

    // First subarray is arr[l..m]

    // Second subarray is arr[m+1..r]

    void merge(int arr[], int l, int m, int r)

    {

        // Find sizes of two subarrays to be merged

        // Create two temp arrays of sizes calculated above

        // Copy data from parameter (original) array to temp arrays     

        // Merge the temp arrays into original array

        // Copy remaining elements of left subarray if any

        // Copy remaining elements of right subarray if any 

    }

    // Main function that sorts arr[l..r] using merge() method, above.

    void sort(int arr[], int l, int r)

    {

        if (l < r) {

            // Find the middle point

            // Sort first and second halves

            sort(??);  // sort the first half of the original array

            sort(??);  // sort the second half of the original array

            // Merge the two sorted halves of the original array into the original array 

            merge(???); 

        }

    }

    // Driver code

    public static void main(String args[])

    {

        int arr[] = { 12, 11, 13, 5, 6, 7 };

        System.out.println("Given Array");

        printArray(arr);

        MergeSort ob = new MergeSort();

        ob.sort(arr, 0, arr.length - 1);

        System.out.println("\nSorted array");

        printArray(arr);

    }

}