Each digit in each row needs to be compared to its base value, so the running time per row is O(n). Thus, the overall time complexity is O(nlogn). If you are unlucky enough to select the minimum value as the base value each time, you will need to move the other data to the right of the base value each time and execute n rows recursively, resulting in O(n2) running time. This is the same thing as picking the minimum every time and moving it to the leftmost, which is the same thing as selecting sort. In addition, if every number in the data is equally likely to be chosen as the base value, the average running time required is O(nlogn).
