Time complexity of numpy.sort

In this example we will look into the time complexity of numpy.sort()

import numpy as np
from neurtu import timeit, delayed


rng = np.random.RandomState(42)


df = timeit(delayed(np.sort, tags={'N': N, 'kind': kind})(rng.rand(N), kind=kind)
            for N in np.logspace(2, 5, num=5).astype('int')
            for kind in ["quicksort", "mergesort", "heapsort"])

print(df.to_string())

Out:

                  wall_time
N      kind
100    quicksort   0.000005
       mergesort   0.000006
       heapsort    0.000006
562    quicksort   0.000010
       mergesort   0.000018
       heapsort    0.000036
3162   quicksort   0.000171
       mergesort   0.000185
       heapsort    0.000293
17782  quicksort   0.001220
       mergesort   0.001302
       heapsort    0.001975
100000 quicksort   0.007537
       mergesort   0.009352
       heapsort    0.015456

we can use the pandas plotting API (that requires matplotlib)

ax = df.wall_time.unstack().plot(marker='o')
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_ylabel('Wall time (s)')
ax.set_title('Time complexity of numpy.sort')