Now lets consider the pseudocode for the procedure SortDoubled which will sort the doubled cycled shifts of length to L, given the string S. The current length L, the order of the current shifts of length L, and their equivalents classes in the array class. We'll start with initializing the array count with the zero array of size equal to the length of the string this is the standard array for counting sort, but as oppose to sort characters procedure it will sort not characters, but equivalents classes of cyclic shift of length L. And there are at most length of S difference including classes that's why we initialized the array with size length of the string. As opposed to sort characters where we initialized it with the size of the alphabet. We'll also need another array new order, which will store our answer. It will be the order of the sorted doubled cyclic shift. We initialize it with area of size, length of S. The next two four loops are standard four loops for the counting sort. When we first count the number of occurrences of each equivalence class of single cyclic shifts and then we compute the partial sums of that counting array and the last four loop of the counting sort needs to go through the array. We're going to sort from the end to the beginning and that is important for the sort to be stable. So, we need to go through the array of double cyclic shifts which are initially sorted by their second half in the reverse order. But you don't want to actually build this array of doubled cyclic shifts and then go through it in reverse order. We want to only build this array in our head and in the code, we just want to go through this array in the reverse order. So how to do that? Remember that we have the array order, and if we go in the direct order of this array, we'll go through all the cyclic shifts of length L in increasing order. What we need instead is, first, to go not through cyclic shifts of length L, but through cyclic shifts of length to L which starts exactly L counter clockwise from those. And that is why we decrease order I by L and at length of the string and take modulo S, just because we're going through a circle. And we need to go downwards from the last i to the first i, because we need to go in the reverse order. So these two lines for i from length of S- 1 down to 0. And the last line which assigns variable starts to order i minus L plus length of string s module s. What they basically do is they go with variable start in the reverse order through the array of double cyclic shifts. Sorted by their second half. So start goes through the starts of those double cyclic shifts in the reverse order. Now, everything else that happens in this for loop is just regular counting sort. We take the class of this start position, which is the class of the first half of the corresponding doubled shift by which we want to sort. Then we go and decrease the partial sum corresponding to that equivalence class in our counting array. And then we just put our start in the position which the counting sort prescribes to it. So these three lines from getting the clust of the start position decreasing the partial sum and assigning the start to the position counter of clause are the three standards lines of the counting sort. The complexity here is that start is going in the reverse order. Through the array of double cyclic shifts sorted by their second half and that we instead of comparing characters or something else we compare equivalence classes of the single cyclic shift. So this is what this last forlob does. And in the end what we have is the array new order. Which contains the double cyclic shifts which were initially sorted by their second half and then we sorted them by count and sort, by their first half. And so now they are sorted by the first half and the count and sort was stable. So in case when their first part, first half is the same, they're also sorted by the second half, because they were sorted by second half initially. So new order finally contains all the dabbled cyclic shifts in the correct order, in the sorted order. So this is the function that sorts all the doubled cyclic shifts. And the running time of this procedure is linear because this is basically the regular counting sort. Although it sorts very complex objects, in practice in the code, it just sorts integers, the equivalent classes of the single cyclic shifts and it does so in the running time of the counting sort which runs in the time number of items plus number of different values. Number of items is equal to length of the string and the number of different values of a clauses is also to smallest length of the stream. So all in all, those three for loops run in linear time. In the next video, we will talk about how to update the classes of those double cyclic shifts after they are sorted, and how to finally build the suffix array from scratch.
