More

    [ALGORITHM] MERGE SORT

    To understand merge sort you should be aware about recursion and divide and conquer technique.  

    In Merge sort, we divide the array into smaller segments recursively until there is only 1 element in each array segment. Then the array segments with single elements are merged in sorted form to form bigger and bigger sorted array segments. During every merge, we will be combining two sorted arrays and creating a combined sorted array.

    Algorithm: Merge Sort

    public void mergeSort (int arr[], int low, int high){

                int mid;

                   if (low< high){

                                  mid= (low+high)/2;

                                  mergeSort (arr, low, mid);

                                  mergeSort (arr, mid+1, high);

                                  merge (arr, low, mid, high);

                }

    }

    public void merge (int arr[], int low, int mid, int high){

                int size = high-low+1;

                int temp[] = new int [size];

                int currentLow=low;

                int currentHigh=mid+1;

                int current=0;

                   while ( (currentLow <=mid) && (currentHigh <=high) ){

                                  if (arr [currentLow ]< arr [currentHigh]){

                                              temp [current] = arr[currentLow];

                                              currentLow++;

                               }

                                  else{

                                              temp [current]=arr [currentHigh];

                                              currentHigh++;                                            

                               }

                               current++;

                }

                //If currentHigh has reached high first

                   while (currentLow <= mid){

                               temp[current]=arr[currentLow];

                               currentLow++;

                               current++;

                }

                //if currentLow has reached mid but currentHigh has not reached high, we can leave remaining

                // elements in their current sorted position, copy sorted elements to arr.

                   for ( int i=0; i< current; i++){

                               arr [low] =temp[i];

                               low++;

                }

    }

    We use the input array and a temporary buffer array to do merge sort. We divide the array in half, sorts each of those halves using recursion, and then merges them back together. Eventually you merge two single element arrays as you keep on dividing and calling mergeSort through recursion.

    Every time, we will merge back two sorted segments of the input array. We will copy the sorted segments to a new temporary array in sorted order, and then we will write them back to the original array. First while loop execute

    First we divide the input array and then we will merge it in sorted form. The recursive division is done by the below code segment:

    if (low< high){

      mid= (low+high)/2;

      mergeSort (arr, low, mid);

      mergeSort (arr, mid+1, high);

    Low < high checks for recursion termination condition, which means, as long as there are more than one element, divide and call recursion again.

    [67544321]

     [6754] [4321]

     [67] [54] [43]    [21]   

     [6] [7] [5] [4] [4] [3] [2] [1]   

    Merge is done by the merge method which is called after all the recursive calls. The merge method simply takes two sorted array segments and creates a merged sorted array. First it will combine two one element array segments, then merge them with bigger sorted arrays and so on.  

    [6] [7] [5] [4] [4] [3] [2] [1]   

     [67] [54] [34] [21]    

     [4567] [1234]   

    [12344567]

    In the merge method, we use the input array and a temporary buffer array to do merge. We will copy the sorted segments to a new temporary array in sorted order, and then we will write them back to the original array. First while loop executes until currentLow reaches high i.e, atleast when one of the segment ends. The remaining elements in the other segment will be larger than already added ones and in sorted order. So we can just copy them to the end of the new temporary array. We will do this by copying the remaining elements in segment one (left) to the temp array if currentHigh has reached high. However we don’t have to do this in case currentLow has reached mid. The remaining elements in segment two (right) will be eventually in their current position itself even if we copy them to the new array and copy back to the original array there. Finally, we will copy the contents of new temporary array from its beginning till current (last element added) position, into the original array from low till current.

    Important Notes on Merge Sort

    • Merge sort accesses the date in a sequential manner.
    • Merge sort can be used for sorting a linked list.
    • Merge sort is insensitive to the initial order of input.
    • Merge of the merge sort starts with the small sub-lists and finishes up with the largest one and hence it doesn’t need stack. Hence this algorithm is more stable than similar ones like quicksort.
    • Performance of Merge sort is 0 (n log n) in all cases.

    How to learn an algorithm faster and easier?

    Every time you learn an algorithm, the best approach to understand it is to try it out using a pen and paper. Take a sample input; go through each step and iteration writing down all variable values. After each of the iterations, you will understand more and more.

    Recent Articles

    OAUTH – FREQUENTLY ASKED QUESTIONS FOR INTERVIEWS AND SELF EVALUATION

    Why is refresh token needed when you have access token? Access tokens are usually short-lived and refresh tokens are...

    SUMO LOGIC VIDEOS AND TUTORIALS

    Sumo Logic Basics - Part 1 of 2 (link is external) (Sep 29, 2016)Sumo Logic Basics - Part 2 of 2...

    GIT – USEFUL COMMANDS

    Discard all local changes, but save them for possible re-use later:  git stash Discarding local changes...

    DISTRIBUTED COMPUTING – RECORDED LECTURES (BITS)

    Module 1 - INTRODUCTION Recorded Lecture - 1.1 Introduction Part I – Definition

    BOOK REVIEW GUIDELINES FOR COOKBOOKS

    Whenever you add reviews for the book, please follow below rules. Write issues in an excel.Create an excel...

    Related Stories

    Leave A Reply

    Please enter your comment!
    Please enter your name here

    Stay on op - Ge the daily news in your inbox