Merge Sort Flashcards

1
Q

MergeSort
definition

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

MergeSort
Complexity

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

MergeSort
Function code

A

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);
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Merge Function

A

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++;
    }
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Merge sort step 1

A

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];
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Merge sort step 2

A

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++;
       }
   }
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Merge sort step 3

A

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);
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Merge helper step 1

A

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;
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Merge helper step 2

A

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++;
}
}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Merge helper step 3

A

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++;
}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly