Merge Sort

Question 1

MergeSort
definition

Answer 1

A recursive algorithm that recursively divides an array in 2, then sorts, and then re-combines the array

Question 2

MergeSort
Complexity

Answer 2

Run-time= O(n log n)
Space = O(n)

Question 3

MergeSort
Function code

Answer 3

private static void mergeSort(int[] array) {
int length = array.length;
if(length <= 1) return;

    int mid = length/2;

   int[] leftarr = new int[mid];
   int[] rightarr = new int[length - mid];

   int i = 0;
   int j = 0;

   for(; i < length; i++){
       if(i < mid){
           leftarr[i] = array[i];
       }
       else{
           rightarr[j] = array[i];
           j++;
       }
   }

   mergeSort(leftarr);//recurssion
   mergeSort(rightarr);
   merge(array,leftarr,rightarr);
}

Question 4

Merge Function

Answer 4

private static void merge(int[] array,int[] leftArray,int[] rightArray) {
int leftSize= leftArray.length;
int rightSize = rightArray.length;

    int i=0, l=0,r=0;

    while ( l< leftSize && r< rightSize){
        if(leftArray[l]< rightArray[r]){
            array[i] = leftArray[l];
            i++;
            l++;
        }
        else{
            array[i] = rightArray[r];
            i++;
            r++;
        }
    }
    while( l< leftSize){
        array[i] = leftArray[l];
        i++;
        l++;
    }
    while( r< rightSize){
        array[i] = rightArray[r];
        i++;
        r++;
    }
}

Question 5

Merge sort step 1

Answer 5

Create variables to store the size of the array and the midpoint
Then 2 arrays to store the left and right hand side of the array.

int length = array.length;
if(length <= 1) return;

    int mid = length/2;

   int[] leftarr = new int[mid];
   int[] rightarr = new int[length - mid];

Question 6

Merge sort step 2

Answer 6

Declare indicies for each array.
Using a for loop iterate through the entire array copying everything before the mid point to the left array and everything after the midpoint to the right array.

int i = 0;
int j = 0;

   for(; i < length; i++){
       if(i < mid){
           leftarr[i] = array[i];
       }
       else{
           rightarr[j] = array[i];
           j++;
       }
   }

Question 7

Merge sort step 3

Answer 7

Implement recursion for each of the arrays to continue to divide them. Then call the merge helper function that rebuilds the array.

   mergeSort(leftarr);//recurssion
   mergeSort(rightarr);
   merge(array,leftarr,rightarr);

Question 8

Merge helper step 1

Answer 8

Create variables to store the length of each of the two arrays. Then create indicies for each of the arrays including the original.

int leftSize= leftArray.length;
int rightSize = rightArray.length;

    int i=0, l=0,r=0;

Question 9

Merge helper step 2

Answer 9

Check conditions for merging using a while loop to ensure there are elements in both arrays to compare. Then compare the elements using an if.

while ( l< leftSize && r< rightSize){
if(leftArray[l]< rightArray[r]){
array[i] = leftArray[l];
i++;
l++;
}
else{
array[i] = rightArray[r];
i++;
r++;
}
}

Question 10

Merge helper step 3

Answer 10

Add two more while loops for if there is one element left in either the left or right array.

while( l< leftSize){
array[i] = leftArray[l];
i++;
l++;
}
while( r< rightSize){
array[i] = rightArray[r];
i++;
r++;
}