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
Post a Comment