advanced data structures and implementation the same situation occurs on the next comparison between pair of 'sthe second comparison is between index ( cand index ( )so the element from the first group advances sa for sa for and final sa input index at this pointthere are no ties for whileso we quickly advance to the last characters of each groupsa for sa for and final sa input index finallywe get to the end the comparison between two ' requires that we compare the next characterswhich are at indices and since this comparison is between an element and an elementas we saw beforewe cannot look up the result and must compare directly but those are also the sameso now we have to compare indices and which is an automatic winner for index (since it is past the end of the stringthus the in index advancesand then we can finish the merge notice that had we not been at the end of the stringwe could have used the fact that the comparison is between an element and an elementwhich means the ordering would have been obtainable from the suffix array for