There are two quicksort partition methods mentioned in Cormen:

(the argument A is the array, and [p, r] is the range, inclusive, to perform the partition on. The returned value is the index to the pivot after the partition.)

Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
        j = j - 1
    until A[j] <= x
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
        return j


Lomuto-Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        swap( A[i], A[j] )
swap( A[i + 1], A[r] )
return i + 1

Disregarding the method of choosing the pivot, in what situations is one preferable to the other? I know for instance that Lomuto preforms relatively poorly when there is a high percentage of duplicate values ( i.e. where say more than 2/3rds the array is the same value ), whereas Hoare performs just fine in that situation.

What other special cases make one partition method significant better than the other?

  • 3
    $\begingroup$ I can't think of any situation in which Lomuto is better than Hoare. It seems like Lomuto performs extra swaps whenever A[i+1] <= x. In a sorted array (and given reasonably chosen pivots) Hoare does almost no swaps and Lomuto does a ton (once j gets small enough then all the A[j] <= x.) What am I missing? $\endgroup$ Commented Apr 21, 2013 at 13:05
  • 5
    $\begingroup$ @WanderingLogic I'm not sure, but it seems Cormen's decision to use the Lomuto partition in his book may be pedagogical - it seems to have a fairly straight-forward loop invariant. $\endgroup$ Commented Apr 21, 2013 at 17:05
  • 2
    $\begingroup$ Note that those two algorithms don't do the same thing. At the end of Hoare's algorithm, the pivot is not at it's final place. You could add a swap(A[p], A[j]) at the end of Hoare's to get the same behaviour for both. $\endgroup$
    – Mmmh mmh
    Commented Oct 15, 2014 at 12:32
  • $\begingroup$ You should also check for i < j in the 2 repeat loops of Hoare's partitioning. $\endgroup$
    – Mmmh mmh
    Commented Oct 15, 2014 at 12:33
  • $\begingroup$ @AurélienOoms The code is copied directly from the book. $\endgroup$ Commented Oct 15, 2014 at 13:54

2 Answers 2


Pedagogical Dimension

Due to its simplicity Lomuto's partitioning method might be easier to implement. There is a nice anecdote in Jon Bentley's Programming Pearl on Sorting:

“Most discussions of Quicksort use a partitioning scheme based on two approaching indices [...] [i.e. Hoare's]. Although the basic idea of that scheme is straightforward, I have always found the details tricky - I once spent the better part of two days chasing down a bug hiding in a short partitioning loop. A reader of a preliminary draft complained that the standard two-index method is in fact simpler than Lomuto's and sketched some code to make his point; I stopped looking after I found two bugs.”

Performance Dimension

For practical use, ease of implementation might be sacrificed for the sake of efficiency. On a theoretical basis, we can determine the number of element comparisons and swaps to compare performance. Additionally, actual running time will be influenced by other factors, such as caching performance and branch mispredictions.

As shown below, the algorithms behave very similar on random permutations except for the number of swaps. There Lomuto needs thrice as many as Hoare!

Number of Comparisons

Both methods can be implemented using $n-1$ comparisons to partition an array of length $n$. This is essentially optimal, since we need to compare every element to the pivot for deciding where to put it.

Number of Swaps

The number of swaps is random for both algorithms, depending on the elements in the array. If we assume random permutations, i.e. all elements are distinct and every permutation of the elements is equally likely, we can analyze the expected number of swaps.

As only relative order counts, we assume that the elements are the numbers $1,\ldots,n$. That makes the discussion below easier since the rank of an element and its value coincide.

Lomuto's Method

The index variable $j$ scans the whole array and whenever we find an element $A[j]$ smaller than pivot $x$, we do a swap. Among the elements $1,\ldots,n$, exactly $x-1$ ones are smaller than $x$, so we get $x-1$ swaps if the pivot is $x$.

The overall expectation then results by averaging over all pivots. Each value in $\{1,\ldots,n\}$ is equally likely to become pivot (namely with prob. $\frac1n$), so we have

$$ \frac1n \sum_{x=1}^n (x-1) = \frac n2 - \frac12\;. $$

swaps on average to partition an array of length $n$ with Lomuto's method.

Hoare's Method

Here, the analysis is slightly more tricky: Even fixing pivot $x$, the number of swaps remains random.

More precisely: The indices $i$ and $j$ run towards each other until they cross, which always happens at $x$ (by correctness of Hoare's partitioning algorithm!). This effectively divides the array into two parts: A left part which is scanned by $i$ and a right part scanned by $j$.

Now, a swap is done exactly for every pair of “misplaced” elements, i.e. a large element (larger than $x$, thus belonging in the right partition) which is currently located in the left part and a small element located in the right part. Note that this pair forming always works out, i.e. there the number of small elements initially in the right part equals the number of large elements in the left part.

One can show that the number of these pairs is hypergeometrically $\mathrm{Hyp}(n-1,n-x,x-1)$ distributed: For the $n-x$ large elements we randomly draw their positions in the array and have $x-1$ positions in the left part. Accordingly, the expected number of pairs is $(n-x)(x-1)/(n-1)$ given that the pivot is $x$.

Finally, we average again over all pivot values to obtain the overall expected number of swaps for Hoare's partitioning:

$$ \frac1n \sum_{x=1}^n \frac{(n-x)(x-1)}{n-1} = \frac n6 - \frac13\;. $$

(A more detailed description can be found in my master's thesis, page 29.)

Memory Access Pattern

Both algorithms use two pointers into the array that scan it sequentially. Therefore both behave almost optimal w.r.t. caching.

Equal Elements and Already Sorted Lists

As already mentioned by Wandering Logic, the performance of the algorithms differs more drastically for lists that are not random permutations.

On an array that is already sorted, Hoare's method never swaps, as there are no misplaced pairs (see above), whereas Lomuto's method still does its roughly $n/2$ swaps!

The presence of equal elements requires special care in Quicksort. (I stepped into this trap myself; see my master's thesis, page 36, for a “Tale on Premature Optimization”) Consider as extreme example an array which filled with $0$s. On such an array, Hoare's method performs a swap for every pair of elements - which is the worst case for Hoare's partitioning - but $i$ and $j$ always meet in the middle of the array. Thus, we have optimal partitioning and the total running time remains in $\mathcal O(n\log n)$.

Lomuto's method behaves much more stupidly on the all $0$ array: The comparison A[j] <= x will always be true, so we do a swap for every single element! But even worse: After the loop, we always have $i=n$, so we observe the worst case partitioning, making the overall performance degrade to $\Theta(n^2)$!


Lomuto's method is simple and easier to implement, but should not be used for implementing a library sorting method.


In this answer, I explained why a good implementation of the “crossing-pointer scheme” from Hoare's partitioning method is superior to the simpler scheme of Lomuto's method, and I stand by everything I said on that topic.
Alas, this is strictly speaking not what the OP was asking!

The pseudocode for Hoare-Partition as given above does not have the desirable properties I lengthily praised, since it fails to exclude the pivot element from the partitioning range. As a consequence, the pivot is “lost” in the swapping and cannot be put into its final position after partitioning, and hence be excluded it from recursive calls. (That means the recursive calls do no longer fulfill the same randomness assumptions and the whole analysis seems to break down! Robert Sedgewick's PhD dissertation discusses this issue in detail.)

For pseudocode of the desirable implementation analyzed above, see my master's thesis, Algorithm 1.(That code is due to Robert Sedgewick).

  • 20
    $\begingroup$ Wow, that's one detailed answer. Nicely done! $\endgroup$
    – Raphael
    Commented Apr 25, 2013 at 7:49
  • 1
    $\begingroup$ Have to agree with Raphael, really nice answer! $\endgroup$ Commented Apr 26, 2013 at 7:11
  • 1
    $\begingroup$ I would make a small clarification, that as the ratio of unique elements to total elements gets lower, the number of comparisons that Lomuto does grows significantly faster than those of Hoare. This is likely due to poor partitioning on Lomuto's part and good average partitioning on Hoare's part. $\endgroup$ Commented May 13, 2013 at 6:37
  • 1
    $\begingroup$ Great explanation of the two methods! Thank you! $\endgroup$
    – vkoukou
    Commented Apr 26, 2017 at 21:23
  • 1
    $\begingroup$ You can easily create a variant of Lomuto method that can extract all elements that are equal to the pivot, and leave them out of recursion, though I am not sure if it would help or hinder average case. $\endgroup$ Commented Oct 19, 2019 at 22:06

Some comments added to the excellent Sebastian answer.

I'm going to talk about the partition rearrangements algorithm in general and not about its particular use for Quicksort.


Lomuto's algorithm is semistable: the relative order of the elements not satisfying the predicate is preserved. Hoare's algorithm is unstable.

Element Access Pattern

Lomuto's algorithm can be used with singly linked list or similar forward-only data structures. Hoare's algorithm needs bidirectionality.

Number of Comparisons

Lomuto's algorithm can be implemented performing $n-1$ applications of the predicate to partition a sequence of length $n$. (Hoare's too).

But in order to do this we have to sacrifice 2 properties:

  1. The sequence to be partitioned must not be empty.
  2. The algorithm is unable to return the partition point.

If we need any of these 2 properties, we will have no choice but to implement the algorithm by making $n$ comparisons.

  • $\begingroup$ Thanks Fernando. QQ: What exactly do you mean by "predicate" here? $\endgroup$
    – Josh
    Commented Apr 28, 2020 at 15:52
  • $\begingroup$ @Josh A predicate is a functional procedure returning a truth value. $\endgroup$ Commented Apr 29, 2020 at 19:55
  • $\begingroup$ It is never said that the pivot value needs not be a value present in the array (though this is a quite natural choice). But it is essential that the partition does not leave one of the subarrays empty. $\endgroup$
    – user16034
    Commented Mar 22, 2022 at 8:16
  • $\begingroup$ The Lomuto algorithm is only "semi stable" in the sense that the elements moved into the lower partition are in original relative order, whereas the elements swapped into the upper partition are scambled. Needless to say, this is of no significance or use, and doesn't bring about a stable sort. A left to right scan of sequence can partition it into two sequences in a stable way; but that is not the Lomuto algorithm. $\endgroup$
    – Kaz
    Commented May 4, 2023 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.