Before:

After:

The algorithm

  1. Select a random pivot (ours is the number 3)

  2. Pick the left pointer and the right pointers

    • Left pointer must be the first element of the array.
    • Right pointer must be the last element of the array (exclude the pivot element)
  3. Start with the left pointer

    If true (that the element value is less or equal to the pivot’s value), move the pointer to the right:

    If false, the left pointer stops (loses its turn).

  4. Right pointer’s turn

    True. If element value is greater than the pivot’s value, move right pointer to the left:

    Else false:

    Switch the values between the two pointers. This moves the lesser number to the left and the greater number to the right:

    Right pointer stops (loses its turn).

  5. Left pointer’s turn

    Move left pointer to the right:

    If true, move pointer to the right and make the comparison again:

  6. If left pointer’s value is not lesser than pivot’s value

    Switch the values between the left pointer’s value with the pivot’s value :

  7. This first pass is done. Notice that the values to the left of the pivot are sorted but the right side are not.

    As long as this is the case, you have to do steps 1 to 6 again and again until both sides are properly sorted.