Note that the pseudo-code in wiki is not practical. It is written to undestand.
If an array is [0,0,0,1] pivot is 1 and other elements are less than the pivot,
then swapping(t <-- a, a <-- b, b <--t) works as t <-- a, a <-- a, a <-- t.
In this case swapping works nothing.
If an array is [4,2,1,3] then [4,2,1,3] --> [2,4,1,3] --> [2,1,4,3] --> [2,1,3,4].
In this case '4' moves like in bubble sort.
Performance comparison is difficult, because it depends on some factors.
- Implementation
Good code run fast, ugly code run slow, you know. - Data size
a. Size of array element.
b. Whole array size exceed a cache memory or not.
c. Whole array size exceed a main memory or not. - Data structure
a. An array is stored in a continuous memory as C language.
This is the fastest if whole array size exceed a cache memory.
b. An array consist of pointers to a continuous memory.
c. Pointer is gotten by malloc(3) or "new" operator. - Data spread
If random number is used then ESD(estimated standard deviation) of processing time is 5%. Not used then 2%. I researched. - OS, H/W
Linux/Unix, microsoft windows is multi-task OS. Program is often interrupted.
Many core CPU is better. Test before GUI login is better. Single-task OS is better.
Example: N=100000, 32 byte/element, pivot is a middle element, strcmp(3), continuous memory
qsort_middle() usec = 522870 call = 999999 compare = 28048465 copy = 15404514
merge_sort() usec = 533722 call = 999999 compare = 18673585 copy = 19673584
Source C programs and scripts are posted in github. Thre is various quicksort and merge sort.