CODEWITHSUNDEEP
javaarraysalgorithmsortingmergesort
john lee
john lee

Reputation: 55

Merge Sort tracing clarification

I'm having a little difficulty of tracing the process of merge sort... Conceptually, I understand that an unsorted array will be divided until its sub-arrays of sub-arrays become the length of 1, in which it becomes an array that contains 1 elements each, that is said to be sorted. Using

 mergeSort(A,p,r) //where p = lowest index, r = highest
     if (p < r) {
         q = (p+r) / 2
         mergeSort(A,p,q)
         mergeSort(A,q+1,r)
         merge(A,p,q,r) 
     }

on an unsorted array of say [3, 5, 2, 1, 6, 4] where p is an index at element 3, q being an index of element 2 and r being the index at element 4. From my understanding, it will first be divided into [3, 5, 2] due to invoking mergeSort(A,p,q); now the new indices will be p at element 3, q at element 5, r at element 2; so [3, 5, 2] will be divided to [3, 5] with p and q being indices at element 3, r being index at element 5; which will be divided to [3]. My question is, is [2] (which is from [3, 5, 2] after division) be of indexed as p or q+1?

.... Actually, I feel like my question isn't clear enough so to ask it in another way, since [3, 5, 2, 1, 6, 4] will be divided into [3, 5, 2] and [1, 6, 4]; which will be divided into [3, 5] and [2] ; [1, 6] and [4]; which will also be divided to [3] [5] and [1] [6]; which part of the divisions invoke mergeSort(A,p,q) and which part of the division invoke mergeSort(A,q+1,r)? are [1, 6, 4] also indexed as p at element 1, r at element 4?

Upvotes: 1

Views: 979

Answers (1)

user2736738
user2736738

Reputation: 30926

The easiest way to track this is take a pencil and paper. And do it for yourself.

Any rule to follow? Yes when you call a function then that funstion is executed. (or your attention should be in that function) .

What I mean is:-

mergesort([3, 5, 2, 1, 6, 4]) you called.

Then eventually you face this line

     q = (p+r) / 2
     mergeSort(A,p,q)   [3,5,2] <------
     mergeSort(A,q+1,r) [1,6,4]
     merge(A,p,q,r)

Now your attention should be in mergesort( [3,5,2] )

This way you will go on. And at some point you will reach this line.

     q = (p+r) / 2
     mergeSort(A,p,q)   [2,3,5] // this is sorted now
     mergeSort(A,q+1,r) [1,6,4] <--------
     merge(A,p,q,r)

And go on like this. This way you at one point will invoke merge which will merge the sorted subarrays into the complete sorted array.

  • Don't bother yourself mergeSort(A,q+1,r) when you are sorting mergeSort(A,p,q). This si seuqntially processed not parallely so unless this subarray is sorted the other portion is not called.

As answer to your second question let me show you another picture.

 [3, 5, 2, 1, 6, 4]
  p     q        r
       /\
[3,5,2]  [1, 6, 4]
 p q r    p  q  r
  |   \       |    \ 
[3,5] [2]  [1, 6]  [4]
 p r        p  r
 q          q
 /  \        |\
[3] [5]     [1] [6]

This is the way the mergesort are called on the array.

And in recusrion every function call has its own parameters. What serves as q in the parent array in child array it will serve as p or r.

Upvotes: 2

Related Questions