CODEWITHSUNDEEP
javaalgorithmsortingmerge
jn025
jn025

Reputation: 2895

Trouble understanding merge sorts merge part of the algorithm

I'm having a little bit of trouble understanding the 'merge' part of the merge sort algorithm in that I'm trying to make sense of parts of the algorithm in context and certain variables/loops aren't making sense to me. I understand the recursive divide process and the sort aspect of the merge but in this particular merge algorithm:

    public static void merge(int data[], int temp[], int low, int middle, int high){
    int ri=0; //result index
    int ti=low;//temp index
    int di=middle;//data index
    int[] result = new int[high-low+1];

    while (ti<middle && di<=high){
      if (data[di]<temp[ti]){
        result[ri++] = data[di++];//smaller is in data
       } 
       else{
            result[ri++] = temp[ti++];//smaller is in temp
            }
    } 

while(ti<middle) result[ri++]=temp[ti++];
while(di<=high) result[ri++]=data[di++];
for(int i=0;i<high;i++) data[low+i]=result[i];

I do not understand the last 3 loops:

while(ti<middle) result[ri++]=temp[ti++];
while(di<=high) result[ri++]=data[di++];
for(int i=0;i<high;i++) data[low+i]=result[i];

Could you explain what these 3 loops are for in the context of merging, and any further advice for better understanding the merge part of the merge sort algorithm?

Upvotes: 1

Views: 51

Answers (1)

kraskevich
kraskevich

Reputation: 18546

The condition of this loop while (ti<middle && di<=high) means that it terminates once there are no more elements in at least one of two halves. But there can still be some elements in another one. That's why we need these two lines:

while(ti<middle) result[ri++]=temp[ti++]; // Remaining elements from the first half.
while(di<=high) result[ri++]=data[di++]; // Remaining elements from the second half.

Now we need to copy the result of merging to the original array. That's exactly what the last line does.

About understanding of the merge phase: Do you understand the algorithm itself(in a mathematical sense, without referring any concrete programming language)? If you don't, than try to fully understand it first without looking at any code. If you do understand the algorithm but not this code, it is fine because this code is pretty bad.

You can take a look at a much more clear implementation:

mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = 
    let (firstHalf, secondHalf) = splitAt (length xs `div` 2) xs
    in merge (mergeSort firstHalf) (mergeSort secondHalf)  

merge xs [] = xs
merge [] ys = ys
merge xs@(x:xt) ys@(y:yt) 
    | x <= y = x : merge xt ys
    | otherwise = y : merge xs yt

Upvotes: 1

Related Questions