CODEWITHSUNDEEP
arraysalgorithmsortingdata-structures
user2644819
user2644819

Reputation: 1827

Merge sort algorithm(merging array part)

Question is about the merge sort from a video starting from 16:43 to 23:34 http://youtu.be/M814OagXWTI?t=16m43s

I am confused how we are merging back these subarrays after exiting our left/right sort merge recursions. Lets start at the very bottom when our elements are split into two subarrays, a left subarray know as B and a right subarray know as C. At around 16:43 we jump into the merge function and sort array B and C which is just 8 and 3. The merge sort function(code bellow) basically compares elements of B with C through indexes. Starting from element 0 we compare each element from both arrays and whichever is smallest gets added to array A. We increase our index of whichever array that element came from etc until we basically have a sorted array. After our sorted array we are finished so we exit the recursion call that we were in to crawl back up the recursion stack that was previously paused and proceed splitting the right side of our subarray 8 3 2 9.

We basically do what we did above and again exit the recursion call that we were in and proceed to merging 3 8 2 9. Okay this is my question: I am seeing a contradiction here in the code. We fed our merged elements back to our Array A but when we call the merge function to merge 2 8 and 2 9 we are passing array B, C, and A. We are then using array B and C to do the comparison but the elements we want to sort are in A are they not? So wouldn't it just be sorting the wrong things? I really need some clarification on this part.

Pseudo code:

 MergeSort(A[0...n-1]){
if n<=1
    return A;

copy A[0...n/2-1] to B[0...n/2-1]
copy A[n/2...n-1] to C[0...n/2-1]
MergeSort(B[0...(n/2)-1)
MergeSort(C[0...(n/2)-1)
Merge(B,C,A)

Merge(B[0...p-1], C[0...q-1], A[0...p+q-1]){
i=0; j=0; k=0
while( i <p and j<q) do{
    if B[i] <= C[j] {
        A[k]=B[i];
        i=i+1;
    }
    else {
    A[k]=C[j];
    j=j+1;
    }
    k=k+1
}

//Copy leftover element
if i==p
    A[k...p+q-1]=C[j...q-1]
else
    A[k...p+q-1]=B[i...p-1]
}

Upvotes: 1

Views: 859

Answers (1)

Patricia Shanahan
Patricia Shanahan

Reputation: 26175

This is a blow-by-blow narration of a simple sort using the quoted algorithm. Indentation represents stack depth. Each MergeSort or Merge invocation is numbered in time order. A3 means the A array in invocation 3. "==" means "is equivalent to". "=" means "has content".

Suppose Top has an array Original, content {3,4,2,1}. Top calls MergeSort(Original)

MergeSort1(A1==Original={3,4,2,1}) Create B1={3,4} and C1={2,1}
  MergeSort2(A2==B1={3,4}) Create B2={3} and C2={4}
    MergeSort3(A3==B2={3}) Base case, no changes.
    MergeSort4(A4==C2={4}) Base case, no changes.
    Merge5(B5==B2={3},C5==B2={4},A5==A2==B1) Write {3,4} into A5, which is A2, which is B1.
  MergeSort6(A6==C1={2,1}) Create B6={2} and C6={1}
    MergeSort7(A7==B6={2}) Base case, no changes.
    MergeSort8(A8==C6={1}) Base case, no changes.
    Merge9(B9==B6={2},C9==C6={1},A9==A6==C1) Write {1,2} into A9, which is A6, which is C1.
  Merge10(B10==B1={3,4},C10==C1=={1,2},A10==A1==Original) Write {1,2,3,4} into A10, which is A1, which is Original.

The high level result of all this is to replace {3,4,2,1} in Original with {1,2,3,4}.

The key point to remember is that each function invocation has its own stack frame, with its own variables, but that its formal argument is mapped to an actual argument that is a variable or parameter in its caller's frame.

Upvotes: 1

Related Questions