Comparing list comprehensions and explicit loops (3 array generators faster than 1 for loop)
<p>I did homework and I accidentally found a strange inconsistency in the speed of the algorithm.
Here is 2 versions of code of same function bur with 1 difference: in first version i use 3 times array generator to filter some array and in second version i use 1 for loop with 3 if statements to do same filter work.</p>

<p>So, here is code of 1st version:</p>

<pre><code>def kth_order_statistic(array, k):
    pivot = (array[0] + array[len(array) - 1]) // 2
    l = [x for x in array if x &lt; pivot]
    m = [x for x in array if x == pivot]
    r = [x for x in array if x &gt; pivot]
    if k &lt;= len(l):
            return kth_order_statistic(l, k)
    elif k &gt; len(l) + len(m):
            return kth_order_statistic(r, k - len(l) - len(m))
    else:
            return m[0]
</code></pre>

<p>And here code of 2nd version:</p>

<pre><code>def kth_order_statistic2(array, k):
    pivot = (array[0] + array[len(array) - 1]) // 2
    l = []
    m = []
    r = []
    for x in array:
        if x &lt; pivot:
            l.append(x)
        elif x &gt; pivot:
            r.append(x)
        else:
            m.append(x)

    if k &lt;= len(l):
        return kth_order_statistic2(l, k)
    elif k &gt; len(l) + len(m):
        return kth_order_statistic2(r, k - len(l) - len(m))
    else:
        return m[0]
</code></pre>

<p>IPython output for 1st version:</p>

<pre><code>In [4]: %%timeit
   ...: A = range(100000)
   ...: shuffle(A)
   ...: k = randint(1, len(A)-1)
   ...: order_statisctic(A, k)
   ...:
10 loops, best of 3: 120 ms per loop
</code></pre>

<p>And for 2nd version:</p>

<pre><code>In [5]: %%timeit
   ...: A = range(100000)
   ...: shuffle(A)
   ...: k = randint(1, len(A)-1)
   ...: kth_order_statistic2(A, k)
   ...:
10 loops, best of 3: 169 ms per loop
</code></pre>

<p>So why first version is faster than second? I also made third version wich using filter() function instead of array generator and it was slower than second version (it got 218 ms per loop)</p>

<p>Let's dissipate that doubt :
The <strong>second version</strong> is slightly faster : <strong>list comprehension are faster</strong>, yet two arrays looping and as much conditionals are discarded in one iteration. </p>

<pre><code>def kth_order_statistic1(array,k):
    pivot = (array[0] + array[len(array) - 1]) // 2
    l = [x for x in array if x &lt; pivot]
    m = [x for x in array if x == pivot]
    r = [x for x in array if x &gt; pivot]

    if k &lt;= len(l):
        return kth_order_statistic1(l, k)
    elif k &gt; len(l) + len(m):
        return kth_order_statistic1(r, k - len(l) - len(m))
    else:
        return m[0]


def kth_order_statistic2(array,k):
    pivot = (array[0] + array[len(array) - 1]) // 2
    l = []
    m = []
    r = []
    for x in array:
        if x &lt; pivot:
            l.append(x)
        elif x &gt; pivot:
            r.append(x)
        else:
            m.append(x)

    if k &lt;= len(l):
        return kth_order_statistic2(l, k)
    elif k &gt; len(l) + len(m):
        return kth_order_statistic2(r, k - len(l) - len(m))
    else:
        return m[0]

def kth_order_statistic3(array,k):
    pivot = (array[0] + array[len(array) - 1]) // 2
    l = []
    m = []
    r = []

    for x in array: 
       if x &lt; pivot: l.append(x)
    for x in array: 
       if x== pivot: m.append(x)
    for x in array: 
       if x &gt; pivot: r.append(x)

    if k &lt;= len(l):
        return kth_order_statistic3(l, k)
    elif k &gt; len(l) + len(m):
        return kth_order_statistic3(r, k - len(l) - len(m))
    else:
        return m[0]

import time
import random
if __name__ == '__main__':

    A = range(100000)
    random.shuffle(A)
    k = random.randint(1, len(A)-1)

    start_time = time.time()
    for x in range(1000) :
        kth_order_statistic1(A,k)
    print("--- %s seconds ---" % (time.time() - start_time))

    start_time = time.time()
    for x in range(1000) :
        kth_order_statistic2(A,k)
    print("--- %s seconds ---" % (time.time() - start_time))

    start_time = time.time()
    for x in range(1000) :
        kth_order_statistic3(A,k)
    print("--- %s seconds ---" % (time.time() - start_time))
</code></pre>

<p><br></p>

<pre><code>python :
--- 25.8894710541 seconds ---
--- 24.073086977 seconds ---
--- 32.9823839664 seconds ---

ipython
--- 25.7450709343 seconds ---
--- 22.7140650749 seconds ---
--- 35.2958850861 seconds ---
</code></pre>

<p>The timing may vary according to the random draw, but the differences between the three are pretty much the same.</p>

python arrays python-2.7 time