Почему моя реализация python сортировки по основанию работает медленнее, чем быстрая сортировка?

У вас тут несколько проблем.

Прежде всего, как указано в комментариях, ваш набор данных слишком мал, чтобы теоретическая сложность могла преодолеть накладные расходы в коде.

Затем ваша реализация со всеми этими ненужными вызовами функций и копированием списков будет очень неэффективной. Написание кода в простой процедурной манере почти всегда будет быстрее, чем функциональное решение (то есть для Python, другие языки здесь будут отличаться). У вас есть процедурная реализация быстрой сортировки, поэтому, если вы напишете свою радикальную сортировку в том же стиле, она может оказаться быстрее даже для небольших списков.

Наконец, может случиться так, что когда вы попробуете использовать большие списки, накладные расходы на управление памятью начнут преобладать. Это означает, что у вас есть ограниченное окно между небольшими списками, где эффективность реализации является доминирующим фактором, и большими списками, где управление памятью является доминирующим фактором.

Вот код, который использует вашу быструю сортировку, но простую радикальную сортировку, написанную процедурно, но пытающуюся избежать такого большого копирования данных. Вы увидите, что даже для коротких списков она превосходит быструю сортировку, но, что более интересно, по мере увеличения размера данных увеличивается и соотношение между быстрой сортировкой и сортировкой по основанию, а затем оно снова начинает падать, поскольку управление памятью начинает доминировать (простые вещи, такие как освобождение список из 1000000 элементов занимает значительное время):

from random import randint
from math import log10
from time import clock
from itertools import chain

def splitmerge0 (ls, digit): ## python (pure!)

    seq = map (lambda n: ((n // 10 ** digit) % 10, n), ls)
    buf = {0:[], 1:[], 2:[], 3:[], 4:[], 5:[], 6:[], 7:[], 8:[], 9:[]}

    return reduce (lambda acc, key: acc.extend(buf[key]) or acc,
        reduce (lambda _, (d,n): buf[d].append (n) or buf, seq, buf), [])

def splitmerge1 (ls, digit): ## python (readable!)
    buf = [[] for i in range(10)]
    divisor = 10 ** digit
    for n in ls:
        buf[(n//divisor)%10].append(n)
    return chain(*buf)

def radixsort (ls, fn = splitmerge1):
    return list(reduce (fn, xrange (int (log10 (max(abs(val) for val in ls)) + 1)), ls))

###############################################################################
# quick sort
###############################################################################

def partition (ls, start, end, pivot_index):

    lower = start
    upper = end - 1

    pivot = ls[pivot_index]
    ls[pivot_index] = ls[end]

    while True:

        while lower <= upper and ls[lower] <  pivot: lower += 1
        while lower <= upper and ls[upper] >= pivot: upper -= 1
        if lower > upper: break

        ls[lower], ls[upper] = ls[upper], ls[lower]

    ls[end] = ls[lower]
    ls[lower] = pivot

    return lower

def qsort_range (ls, start, end):

    if end - start + 1 < 32:
        insertion_sort(ls, start, end)
    else:
        pivot_index = partition (ls, start, end, randint (start, end))
        qsort_range (ls, start, pivot_index - 1)
        qsort_range (ls, pivot_index + 1, end)

    return ls

def insertion_sort (ls, start, end):

    for idx in xrange (start, end + 1):
        el = ls[idx]
        for jdx in reversed (xrange(0, idx)):
            if ls[jdx] <= el:
                ls[jdx + 1] = el
                break
            ls[jdx + 1] = ls[jdx]
        else:
            ls[0] = el

    return ls

def quicksort (ls):

    return qsort_range (ls, 0, len (ls) - 1)

if __name__=='__main__':
    for value in 1000, 10000, 100000, 1000000, 10000000:
        ls = [randint (1, value) for _ in range(value)]
        ls2 = list(ls)
        last = -1
        start = clock()
        ls = radixsort(ls)
        end = clock()
        for i in ls:
            assert last <= i
            last = i
        print("rs %d: %0.2fs" % (value, end-start))
        tdiff = end-start
        start = clock()
        ls2 = quicksort(ls2)
        end = clock()
        last = -1
        for i in ls2:
            assert last <= i
            last = i
        print("qs %d: %0.2fs %0.2f%%" % (value, end-start, ((end-start)/tdiff*100)))

Результат, когда я запускаю это:

C:\temp>c:\python27\python radixsort.py
rs 1000: 0.00s
qs 1000: 0.00s 212.98%
rs 10000: 0.02s
qs 10000: 0.05s 291.28%
rs 100000: 0.19s
qs 100000: 0.58s 311.98%
rs 1000000: 2.47s
qs 1000000: 7.07s 286.33%
rs 10000000: 31.74s
qs 10000000: 86.04s 271.08%

Изменить: просто для пояснения. Реализация быстрой сортировки здесь очень удобна для памяти, она сортируется на месте, поэтому независимо от того, насколько велик список, он просто перетасовывает данные, а не копирует их. Исходная система radixsort эффективно копирует список дважды для каждой цифры: один раз в меньшие списки, а затем еще раз, когда вы объединяете списки. Использование itertools.chain позволяет избежать этой второй копии, но по-прежнему происходит много выделения / освобождения памяти. (Также «дважды» является приблизительным, поскольку добавление списка требует дополнительного копирования, даже если оно амортизировано O (1), поэтому я, возможно, должен сказать «пропорционально дважды».)

Ваше представление данных очень дорогое. Почему вы используете hashmap для своих сегментов? Зачем использовать представление base10, для которого вам нужно вычислять логарифмы (= дорогое вычисление)?

Избегайте лямбда-выражений и тому подобного, я не думаю, что python пока может хорошо их оптимизировать.

Возможно, вместо этого начните с сортировки 10-байтовых строк для теста. И: никаких хэш-карт и подобных дорогих структур данных.