Hi. In this video, we're going to learn how to quickly sort doubled partial cyclic shifts if the partial cyclic shifts of length L are already sorted and their class numbers are known, how to sort them partial cyclic shifts of length 2L. If C_i is a cyclic shift of length L starting in position i and C_i prime is the doubled cyclic shift starting in position i, that is the partial cyclic shift of length 2L starting in position i, then we can represent C_i prime as concatenation of two partial cyclic shifts of length L. That is, C_i prime is concatenation of C_i and C_i plus L. To compare C_i prime with C_j prime, another double partial cyclic shift, it's sufficient to separately compare C_i with C_j and C_i plus L with C_j plus L. To compare them lexicographically, we first compare the first half, C_i and C_j, if they are different than the one which is smaller corresponds to the smaller doubled partial cyclic shift, and if they're equal, then we compare the second halves c_i plus L with C_j plus L. If they're equal, then the whole doubled partial cyclic shifts are also equal. Otherwise, the smaller one corresponds to the smaller doubled partial cyclic shift. You see that in these comparisons, we only use the information of whether one partial cyclic shifts is either in the order than another one and also whether they're equal or not. We have those two sources of information, both the order of partial cyclic shifts of length L and their equivalence classes, so we should be able to use this information to sort the doubled partial cyclic shifts. Let's look at an example of doubled partial cyclic shifts. We have string S, which is ababaa$, and the length L is currently two. We're considering position i equal to 2, then Ci is the same as C_2, which is equal to ab, and C_i plus L is C_2 plus 2, which is equal to C_4, which is aa. C_i prime is the same as C_2 prime, which is the partial cyclic shift of length 4, starting in position 2, which is abaa, which is equal to the concatenation of C_2 and C_4. How do we sort pairs of partial cyclic shifts which we already know how to sort initially? We first can sort the pairs by the second element of the pair and then stable sort by the first element of the pair. Basically, this is the radix sort. If our doubled partial cyclic shifts are already stored by the order of their second pair, then we resort them by the order of their first pair, but we use stable sort. That is, if some first halves are equal, then we don't change their relative order during sorting. Then after these two sorts, first by second half then stable sort by first half, our pairs will be already sorted. Let's look at an example. We have partial cyclic shifts of length 2 already sorted. The string is the same and the partial cyclic shifts are $a, a$, aa, and so on. They are sorted in lexicographic order. Now let's look what if we take partial doubled cyclic shifts by taking the doubled cyclic shifts to the left from the initial partial cyclic shifts. Let's consider these partial cyclic shifts of length L as the right half, the second half of the doubled partial cyclic shifts. That's right, which doubled partial cyclic shift. That would be. For the door a, the doubled partial cyclic shifts that has door a as the second half is aa$a. For a$, the doubled partial cyclic shifts, which ends with the half a$ is baa$. For aa, it is abaa. For ab, it is a$ab. For this ab, it is abab. For this ba, it is baba. For this ba, it is $aba. Now we have the doubled partial cyclic shifts of length 4 sorted by the order of the second halves. Now what we need to do is to resort them by the first half. But in the case when the first halves are equal, we need to avoid breaking the order on the second halves, which is already in the order currently. For example, for the doubled cyclic shifts C_2 prime and C_0 prime, their first halves are equal, but their second halves are already correctly sorted. So while we will be sorting the first halves, although C_2 prime and C_0 prime are equal and their relative order, well, sorting is not relevant, we actually want them to not change their order because it is already correct. This is what achieved by a stable sort algorithm. Another pair is C_3 prime is C_1 prime. Their first halves are also equal, but their second halves are already sorted in the correct order. While sorting, we don't want C_3 prime and C_1 prime to change their relative order, although they're equal. Stable sort is what does that. If we use the stable sort on the first halves, we'll get the order of partial cyclic shifts of length 4. You can check that it is indeed the sorted lexicographic order. You see that in this order, C_2 prime and C_0 prime go in the same order as they were initially, and also C_3 prime and C_1 prime are adjustment and they go in the same order as they were initially. The order is correct. How to actually do all this? Consider C_i prime as doubled cyclic shift starting in position i, and it is a pair of C_i and C i plus L, the first half and the second half. We know that the partial cyclic shifts of length L are already sorted and they go in the order C order of 0, C order of 1, and so on up to C order of length of S minus 1. We want to consider these as second part. We take doubled cyclic shift starting exactly L positions counterclockwise to these corresponding already sorted second halves. Those would be C prime at position order of 0 minus L, C prime at position order of 1 minus L, and so on. C prime order of length of S minus 1 minus L. When I say minus L, I mean of course minus L modular length of the string S because the string is cyclic. These doubled cyclic shifts are already sorted by the second element of pair and the only thing we need to do is to resort them by the order of the first element of the pair. We need a stable sort by first elements of pairs. But we actually know that counting sort is a stable sort, and we know the equivalence classes of single shifts, and we know that the number of equivalence classes is not bigger than the length of the string. We actually can use the counting sort to resort the first halves of these doubled partial cyclic shift. This is the strategy we're going to employ. In the next video, I will show you the implementation of this idea.
