Try to search your question here, if you can't find : Ask Any Question Now ?

# how is sorting faster then linear(low constant)?

HomeCategory: stackoverflowhow is sorting faster then linear(low constant)?

I’ve compared the performances of some built-in sort functions in python 3 verses some algorithms that I know their performances. and I saw some unexpected results. I would like u to clarify those issues.

I used the “perfplot” library to compare the complexity of the algorithms visualized.

``````import numpy as np
import perfplot

# algorithms:

def sort(x):
np.sort(x)
return 0

def sort_c(x):
np.sort_complex(x)
np.sort_complex(x)
return 0

def builtin(x):
sorted(x)
return 0

def c_linear_inplace(x):
for i in range(len(x) - 1):
if x[i] > x[i + 1]:
x[i] = x[i] + x[i + 1]
x[i + 1] = x[i] - x[i + 1]
x[i] = x[i] - x[i + 1]
return 0

def c_linear_outplace(x):
a = x.copy()
for i in range(len(x) - 1):
if x[i] > x[i + 1]:
a[i] = x[i + 1]
a[i + 1] = x[i]
x = a.copy()
return 0

def c_nlogn(x):
logn = int(np.ceil(np.log2(len(x))))
for i in range(len(x)-1):
for j in range(logn):
x[i] = 0
return 0

#comprasion:
perfplot.show(
setup=np.random.rand,  # function to generate input for kernel by n
kernels=[
sort,
sort_c,
builtin,
c_linear_inplace,
c_linear_outplace,
c_nlogn,
],
labels=["sort", "sort_c", "builtin", "check: linear inplace", "check: linear not in place", "check: nlogn"],
n_range=[2 ** k for k in range(15)],  # list of sizes of inputs, i"setup" function will be called with those values
xlabel="len(a)",
)
``````

visual comparaion

I expect all sort functions to be close to the nlogn() function or at least less efficient than the linear ones, and I expect “c_linear_inplace” would be faster than “c_linear_outplace”. but all built-in sort functions were much faster than the linear functions and the “c_linear_outplace” function was slower than the “c_linear_inplace” function.