Logic flow in merge sort [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

how to read and understand mergesort code? I was trying to use debug to track the logic, but it still seems very hard to figure out. Could you shed some light on this for me? Thanks a lot

 static void sort(int[]array, int[] helper, int lower, int upper){
        if(lower == upper){
            return;
        }
        // 6,5,3,1,8,7,2,4
        int mid = lower + (upper - lower) / 2;
        sort(array, helper, lower, mid);
        sort(array, helper, mid+1, upper);

        merge(array, helper, lower, mid+1, upper);

    }

Answer 1

Here's a picture of an array being sorted in real time and one with every sort displayed simultaneously. These are both on the wikipedia merge sort page.

You should not only study the sort function but also the merge function. The sort function is the recursive part of the function whereas the merge function is the meat and potatoes; it's what actually does the sorting part of it.

For example, in the first image below, the sort function is what splits the blocks into groups of 4, 2, and then 1. The merge function is what sorts these blocks, comparing the first value of each group (of size 1, 2, and then 4) and then placing them into the new merged array from lowest to highest.

Answer 2

Here are some comments. Also check out this video, it may help you understand what is going on. The main thing to remember is this is a recursive algorithm, so you solve it by breaking it into smaller parts and running the same algorithm over those smaller parts.

 static void sort(int[]array, int[] helper, int lower, int upper){        
        if(lower == upper){
            // Lower == upper, this means there is only one element, so by definition this is sorted, nothing to do just return
            return;
        }

        // Okay, we have more then one element if we are here.  Our goal here is to sort both the upper half, and lower half independently first.
        //
        // First find the mid point between the upper and lower bounds we are sorting
        // For example if we have an array [6, 5, 3, 1, 8, 7, 2, 4] with lower == 0 and upper == 7 then the mid point is 3
        // Find the mid-point of lower and upper.  This will be used to 
        int mid = lower + (upper - lower) / 2;

        // Now sort both the upper and lower half of the array recursively.
        // Array will look like this to begin with [6, 5, 3, 1, 8, 7, 2, 4]
        sort(array, helper, lower, mid);
        // After sorting from 0 to 3 it will look like this 
        // [1, 3, 5, 6, 8, 7, 2, 4]
        sort(array, helper, mid+1, upper);
        // After sorting from 4 to 7 it will look like this
        // [1, 3, 5, 6, 2, 4, 7, 8]

        // Finally merge the two sorted arrays together.  This is easier now the two halfs are sorted.
        merge(array, helper, lower, mid+1, upper);
        // After we have a sorted array
        // [1, 2, 3, 4, 5, 6, 7, 8]
 }