python - Quicksort not getting quicker -

i learnt how hard people have worked make quicksort quicker. choosing pivot element randomly switching insertion sort smaller arrays , dealing equal keys 3-way partitioning. curious how things worked randomly generated data , thought of profiling python code. attaching script(s) below. problem scripts end taking same amount of time! , when use %prun, looks number of times quicksort gets called quite similar. so, improvements make useful when our data meets worst case (very sorted in wrong direction?)

def hoare_partition(a, lo, hi):      if lo >= hi or (lo + 1) == len(a) - 1:         return none     pivot = a[lo]     left = lo + 1     right = hi       while left <= right , right < len(a):         while left < len(a) , a[left] < pivot:             left += 1         while a[right] > pivot:             right -= 1         if left <= right , right < len(a):             a[left], a[right] = a[right], a[left]             left += 1             right -= 1     a[lo], a[right] = a[right], a[lo]     return right  def hoare_quicksort(a, lo, hi):     ''' vanilla implementation of quick sort. call partition method uses first element pivot '''      if lo < hi:         p = hoare_partition(a, lo, hi)         if p:             #print 'calling ', lo, p - 1             hoare_quicksort(a, lo, p - 1)                #print 'calling ', p + 1, hi             hoare_quicksort(a, p + 1, hi) 

this vanilla implementation select first element pivot. then, changed select midpoint.

so, 1 line gets changed

mid = lo + (hi - lo)//2  a[lo], a[mid] = a[mid], a[lo] pivot = a[lo] 

and random pivot selection, this:

pos = random.randint(lo, hi + 1)   a[lo], a[pos] = a[pos], a[lo] pivot = a[lo] 

now, call them using

%prun hoare_quicksort([random.randint(0, 10000) in xrange(1000)], 0, 999) %prun mid_quicksort([random.randint(0, 10000) in xrange(1000)], 0, 999) %prun random_quicksort([random.randint(0, 10000) in xrange(1000)], 0, 999) 

all of them take same amount of time (5.22, 5.27, 5.61 ms). when call them using %prun , see number of times quicksort gets called, again similar numbers. so, well, what's wrong?

so, improvements make useful when our data meets worst case (very sorted in wrong direction?)

it doesn't have worst case, sort of preexisting order in data nasty things runtime. preexisting order common, , want sort takes advantage of run faster, not 1 looks @ , barfs.

you've tested quicksorts on random data. that's pretty best-case scenario quicksort. if data comes keys of dict, , hash used causes them come out in mostly-sorted order?

>>> data = dict.fromkeys(random.sample(xrange(10000), 9000)).keys() >>> timeit.timeit('rand_quicksort(data[:], 0, len(data)-1)', 'from __main__ impo rt rand_quicksort, data', number=1) 0.06688880239187256 >>> timeit.timeit('hoare_quicksort(data[:], 0, len(data)-1)', 'from __main__ imp ort hoare_quicksort, data', number=1)   # 1000 lines omitted   file "<stdin>", line 9, in hoare_quicksort   file "<stdin>", line 9, in hoare_quicksort   file "<stdin>", line 9, in hoare_quicksort   file "<stdin>", line 9, in hoare_quicksort   file "<stdin>", line 9, in hoare_quicksort   file "<stdin>", line 9, in hoare_quicksort   file "<stdin>", line 9, in hoare_quicksort   file "<stdin>", line 9, in hoare_quicksort   file "<stdin>", line 9, in hoare_quicksort   file "<stdin>", line 4, in hoare_quicksort runtimeerror: maximum recursion depth exceeded 

well, stack overflow, , that's terrible. if didn't, it'd take freaking forever.

(if want reproduce result, note have few bugs in code. if p should if p not none, , random.randint(lo, hi + 1) should random.randint(lo, hi) or random.randrange(lo, hi + 1). had fix proper test results.)