Understanding the sort part of Java Merge sort

Question

I understand how the merge part of the merge sort works, however, for some reason I just cannot wrap my head around the recursive/divide part that occurs before the merge function is called. Using the sample code below, I tried tracing the value of different variables but could not fully understand what is happening.

public void sort(int arr[], int l, int r) { 
    if (l < r) 
    { 
        // Find the middle point 
        int m = (l+r)/2; 

        // Sort first and second halves 
        sort(arr, l, m); 
        sort(arr , m+1, r); 

        // Merge the sorted halves 
        merge(arr, l, m, r); 
    }

}

To me it seems like m keeps getting passed into sort until it becomes 0, so it seems like the 2nd sort() call and the merge() call never execute. Can someone explain the steps that are taken?

This would be a great time to learn how to use the java debugger. It would allow you to view the code and the variables in real time so that you can trace exactly everything that's happening as it happens. — Alex A
– Alex A, Commented Feb 6, 2020 at 22:38
If you are asking about Java's built in sort, it uses Timsort, which is a hybrid insertion + bottom up merge sort. A simpler variation is also a hybrid insertion + bottom up merge sort. An array of n elements is treated as n/k groups of k elements, and each group of k elements is sorted using insertion sort, then the now sorted groups are repeatedly merged breadth first to complete the sort. There's no recursive dividing (generation of indexes) involved. — rcgldr
– rcgldr, Commented Feb 7, 2020 at 3:47

Michael Bianconi · Accepted Answer · 2020-02-06 22:23:40Z

2

Take the following array:

[4][2][5][1][3]

We're going to split it in half:

[4][2][5]    [1][3]

And again:

[4][2]    [5]    [1]    [3]

And again:

[4]    [2]    [5]    [1]    [3]

Notice how we now have 5 sorted arrays (each of length 1). Now it's time to merge them together, sorting as we go. It's a very simple (read: low time-complexity) operation to merge two sorted arrays into a new sorted array:

[2][4]    [1][5]    [3]

Now we have 3 sorted arrays. Let's merge them again:

[1][2][4][5]    [3]

And one final time:

[1][2][3][4][5]

It's now been sorted.

answered Feb 6, 2020 at 22:23

Michael Bianconi

5,2522 gold badges12 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user3552172 Over a year ago

So I understand the concept of how the array should be split, what I would like to know what is happening in each step as the code is being executed. I think the problem is I can’t seem to tie the code to the concept.

Collectives™ on Stack Overflow

Understanding the sort part of Java Merge sort

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related