java - Trouble understanding merge sorts merge part of the algorithm -


i'm having little bit of trouble understanding 'merge' part of merge sort algorithm in i'm trying make sense of parts of algorithm in context , variables/loops aren't making sense me. understand recursive divide process , sort aspect of merge in 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 in data        }         else{             result[ri++] = temp[ti++];//smaller 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 not understand 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 explain these 3 loops in context of merging, , further advice better understanding merge part of merge sort algorithm?

the condition of loop while (ti<middle && di<=high) means terminates once there no more elements in @ least 1 of 2 halves. there can still elements in one. that's why need these 2 lines:

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

now need copy result of merging original array. that's last line does.

about understanding of merge phase: understand algorithm itself(in mathematical sense, without referring concrete programming language)? if don't, try understand first without looking @ code. if understand algorithm not code, fine because code pretty bad.

you can take @ 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 

Comments

Popular posts from this blog

jquery - How do you format the date used in the popover widget title of FullCalendar? -

asp.net mvc - SSO between MVCForum and Umbraco7 -

Python Tkinter keyboard using bind -