CODEWITHSUNDEEP
javasortingmergesort
user3552172
user3552172

Reputation: 23

Understanding the sort part of Java Merge sort

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?

Upvotes: 0

Views: 71

Answers (1)

Michael Bianconi
Michael Bianconi

Reputation: 5232

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.

Upvotes: 2

Related Questions