Merge Sort Flashcards
MergeSort
definition
A recursive algorithm that recursively divides an array in 2, then sorts, and then re-combines the array
MergeSort
Complexity
Run-time= O(n log n)
Space = O(n)
MergeSort
Function code
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); }
Merge Function
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++; } }
Merge sort step 1
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];
Merge sort step 2
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++; } }
Merge sort step 3
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);
Merge helper step 1
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;
Merge helper step 2
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++;
}
}
Merge helper step 3
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++;
}