advanced data structures and implementation [abrindex index of second element radix pass ordering radix pass ordering rank in group sausing ' indices [aca[dab[ra$ add one to above last line of figure stably radix sort by first char using results of previous line using results of previous line figure computing suffix array for step merge the two suffix arrays using the standard algorithm to merge two sorted lists the only issue is that we must be able to compare each suffix pair in constant time there are two cases case comparing an element with an elementcompare the first letterif they do not matchwe are doneotherwisecompare the remainder of (which is an suffixwith the remainder of (which is an suffix)those are already orderedso we are done case comparing an element with an elementcompare at most the first two lettersif we still have matchthen at that point compare the remainder of (which after skipping the two letters becomes an suffixwith the remainder of (which after skipping two letters becomes an suffix)as in case those suffixes are already ordered by sa so we are done examplein our examplewe have to merge sa for sa for and with the first comparison is between index (an )which is an element and index (also an awhich is an element since that is tiewe now have to compare index with index normally this would have already been computedsince index is while index is in howeverthis is special because index is past the end of the stringconsequently it always represents the earlier suffix lexicographicallyand the first element in the final suffix array is we advance in the second group and now we have