> If I understand this statement correctly, I suspect that for some arrays of input keys, the resulting algorithm won't actually sort the keys. That is, we won'

> If I understand this statement correctly, I suspect that for some arrays of input keys, the resulting algorithm won't actually sort the keys. That is, we won't have a sorting algorithm. You don't understand the statement correctly. However, this is not a trivial realization. Because pdqsort always recurses on the left partition first it means that every element to the left of the current recursive call is equal to or less than every element within the current recursive call. So if we find that the selected pivot is equal to an element before the current recursive call we can conclude that there can only be elements equal to the pivot, and not smaller, in the current recursive call. > Maybe your remark "astronomically small" is just a side comment and not relevant to PDQSORT having worst case running time of O( n ln(n) ). Correct. > For this and the associated documentation, I don't see a solid argument that PDQSORT has worst case running time of O( n ln(n) ). There is a very simple argument. The 'bad partition counter' is initially log(n). If we encounter a bad partition, we can do up to O(n) work. This can happen log(n) times. So we can do up to O(n log n) work on bad partitions. If we then encounter another bad partition, we switch to heapsort, which is O(n log n). If we encounter less than log(n) bad partitions Quicksort performed well enough to be O(n log n). For a similar approach, read up on introsort.