I'm not convinced that is the case, for three possibly related reasons:
1. I neglected to mention that I copied someone's implementation and it ran quicker than my merge_sort on this same input.
2. As well as I can remember my own code, I do nothing in the case of ties; It's just one check, move on. Swaps only happen when the accessed index has smaller value than the pivot, which is why I also believe that my code is doing the (almost) minimum number of swaps necessary (one swap for each index less than pivot lying on the right side of pivot).
3. quickSort's worst case involves choosing pivot values on either extreme ends, thus ending up doing the maximum number of swaps, i.e. n-1. E.g. Choosing 9 or 1 in the [9;8;7;6;5;4;3;2;1] array will both result in 8 swaps for the partitioning step; whereas choosing 4 in [4;4;4;4;4;4;4;4;4] will result in no swaps at all (just linear scan and comparison).
@ Corn: Randomized quickSort makes no assumptions about the input's order, due to the internal randomization step. (Random + more random = random // deterministic + random = random). Its runtime is "on average" O(nlogn) regardless what input is given, with a smaller constant coefficient than mergeSort's. Theoretically, quickSort's worst runtime is O(n^2), but this almost never happens (regardless of input). I still haven't quite mastered the proof, though.
1. I neglected to mention that I copied someone's implementation and it ran quicker than my merge_sort on this same input.
2. As well as I can remember my own code, I do nothing in the case of ties; It's just one check, move on. Swaps only happen when the accessed index has smaller value than the pivot, which is why I also believe that my code is doing the (almost) minimum number of swaps necessary (one swap for each index less than pivot lying on the right side of pivot).
3. quickSort's worst case involves choosing pivot values on either extreme ends, thus ending up doing the maximum number of swaps, i.e. n-1. E.g. Choosing 9 or 1 in the [9;8;7;6;5;4;3;2;1] array will both result in 8 swaps for the partitioning step; whereas choosing 4 in [4;4;4;4;4;4;4;4;4] will result in no swaps at all (just linear scan and comparison).
@ Corn: Randomized quickSort makes no assumptions about the input's order, due to the internal randomization step. (Random + more random = random // deterministic + random = random). Its runtime is "on average" O(nlogn) regardless what input is given, with a smaller constant coefficient than mergeSort's. Theoretically, quickSort's worst runtime is O(n^2), but this almost never happens (regardless of input). I still haven't quite mastered the proof, though.