Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.
A merge sort is a type of a divide and conquer algorithm used to sort a given array; this means that the array is divided into halves and then further sub-divided till division can no longer take place.
This happens when you reach a single element array as that has no middle to further divide the array on. Each divided sub-array is then sorted and subsequently merged with other sub-divisions. The sorted merge continues till all divisions of the array have been merged, giving us a sorted array.
Note: Want to learn more about merge sort? Check out our course on popular sorting algorithms.
$$$$
Below is an illustration that shows the basic outline:
Now that we know how the algorithm works in theory, letâ€™s see how to write the code to implement it.
class sorting {public static void merge(int[] left_arr,int[] right_arr, int[] arr,int left_size, int right_size){int i=0,l=0,r = 0;//The while loops check the conditions for mergingwhile(l<left_size && r<right_size){if(left_arr[l]<right_arr[r]){arr[i++] = left_arr[l++];}else{arr[i++] = right_arr[r++];}}while(l<left_size){arr[i++] = left_arr[l++];}while(r<right_size){arr[i++] = right_arr[r++];}}public static void mergeSort(int [] arr, int len){if (len < 2){return;}int mid = len / 2;int [] left_arr = new int[mid];int [] right_arr = new int[len-mid];//Dividing array into two and copying into two separate arraysint k = 0;for(int i = 0;i<len;++i){if(i<mid){left_arr[i] = arr[i];}else{right_arr[k] = arr[i];k = k+1;}}// Recursively calling the function to divide the subarrays furthermergeSort(left_arr,mid);mergeSort(right_arr,len-mid);// Calling the merge method on each subdivisionmerge(left_arr,right_arr,arr,mid,len-mid);}public static void main( String args[] ) {int [] array = {12,1,10,50,5,15,45};mergeSort(array,array.length);for(int i =0; i< array.length;++i){System.out.print(array[i]+ " ");}}}
The code above shows how to write Mergesort in Java. Now letâ€™s understand the code in detail.
The implementation of Merge Sort given above is a recursive one. You start by calling the mergeSort
method as shown on line 51 with the following input parameters:
Now letâ€™s look at the recursive method, mergeSort
which is written from lines 24 to 47.
The method first checks the base case which is, that if the length of the array is less than 2 then return the array as it is, as shown on line 25.
If the base case is not satisfied then the method creates two arrays; the left and right subdivision and recursively calls itself on these two arrays which now contain the copied data of the original array
The last step, on line 46 is that the method calls the merge
method which compares and sorts the left and right arrays.
Now letâ€™s discuss the merge
method written from lines 3 to 22.
The function takes in many parameters; the left array, the right array, the actual array, the sizes of the left and right array.
Now letâ€™s see how the method proceeds:
The first while
loop from lines 7 to 15 checks if the value of both the iterators is less than the respective array size, then it compares which of the element in right_arr
or left_arr
is smaller than the other and chooses that one to place in arr
.
The second while
loop from lines 16 to 18 checks that if only elements in the left_arr
are left then simply append them to arr
The third while
loop from lines 19 to 21 does the same but for the right_arr
.
RELATED TAGS
Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.