How do I improve my quick sort pivot selection in python?
<p>I was originally using only a single random pivot given by </p>

<pre><code>pivots = random.randrange(l,r)
</code></pre>

<p>Here l and r will be integers that define my range</p>

<p>I wanted to improve the run time by greatly increasing the likely hood that my pivot would be a good pivot by selecting the median of three random pivots. Below is the code I used and it caused my run time to increase by 20%-30%. </p>

<pre><code>rr = random.randrange
pivots = [ rr(l,r) for i in range(3) ]
pivots.sort()
</code></pre>

<p>How do I implement the above to be much faster?</p>

<p>Edit: Entire code added below</p>

<pre><code>import random

def quicksort(array, l=0, r=-1):
    # array is list to sort, array is going to be passed by reference, this is new to me, try not to suck
    # l is the left bound of the array to be acte on
    # r is the right bound of the array to act on

    if r == -1:
        r = len(array)

    # base case
    if r-l &lt;= 1:
        return

    # pick the median of 3 possible pivots
    #pivots = [ random.randrange(l,r) for i in range(3) ]
    rr = random.randrange
    pivots = [ rr(l,r) for i in range(3) ]
    pivots.sort()

    i = l+1 # Barrier between below and above piviot, first higher element
    array[l], array[pivots[1]] = array[pivots[1]], array[l]

    for j in range(l+1,r):
        if array[j] &lt; array[l]:
            array[i], array[j] = array[j], array[i]
            i = i+1

    array[l], array[i-1] = array[i-1], array[l]

    quicksort(array, l, i-1)
    quicksort(array, i, r)

    return array
</code></pre>

<p>Edit 2:
This is the corrected code due. There was an error in the algorithm for picking the 3 pivots </p>

<pre><code>import random

def quicksort(array, l=0, r=-1):
    # array is list to sort, array is going to be passed by reference, this is new to me, try not to suck
    # l is the left bound of the array to be acte on
    # r is the right bound of the array to act on

    if r == -1:
        r = len(array)

    # base case
    if r-l &lt;= 1:
        return

    # pick the median of 3 possible pivots
    mid = int((l+r)*0.5)
    pivot = 0
    #pivots = [ l, mid, r-1]
    if array[l] &gt; array[mid]:
        if array[r-1]&gt; array[l]:
            pivot = l
        elif array[mid] &gt; array[r-1]:
            pivot = mid
    else:
        if array[r-1] &gt; array[mid]:
            pivot = mid
        else:
            pivot = r-1

    i = l+1 # Barrier between below and above piviot, first higher element
    array[l], array[pivot] = array[pivot], array[l]

    for j in range(l+1,r):
        if array[j] &lt; array[l]:
            array[i], array[j] = array[j], array[i]
            i = i+1

    array[l], array[i-1] = array[i-1], array[l]

    quicksort(array, l, i-1)
    quicksort(array, i, r)

    return array
</code></pre>

<p>Though it can be outperformed by random choice on occasion, it's still worth looking into the <a href="https://en.wikipedia.org/wiki/Median_of_medians" rel="nofollow">median-of-medians</a> algorithm for pivot selection (and rank selection in general), which runs in O(n) time. It's not too far off of what you are currently doing, but there is a stronger assurance behind it that it picks a "good" pivot as opposed to just taking the median of three random numbers.</p>

python pivot quicksort