Return to Revisions

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.

I suggest a new pseudo-code.

quicksort(A, i, k)
    if i < k
        p := partition(A, i, k)
        quicksort(A, i, p - 1)
        quicksort(A, p + 1, k)

partition(array, left, right)
    hole := choosePivot(Array, left, right)
    pivot := array[hole]        // dig a hole
    array[hole] := array[right]
    hole := right               // move the hole
    while left < hole
        if array[left] >= pivot
            array[hole] := array[left]
            hole := left
            while right > hole
                if array[right] < pivot
                    array[hole] := array[right]
                    hole := right
                right := right - 1
        left := left + 1
    array[hole] := pivot        // bury the hole
    return hole

Performance comparison is difficult, because it depends on some factors.

1. Implementation
   Good code run fast, ugly code run slow, you know.
2. 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.
3. Data structure
   a. An array is stored in a continuous memory as C language.
   b. An array consist of pointers to a continuous memory.
   c. Pointer is gotten by malloc(3) or "new" operator.
4. Data spread
   If random number is used then ESD(estimated standard deviation) of processing time is 5%. Not used then 2%. I researched.
5. 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.