Torch quicksort can be extremely slow

[Michael M]

Hi all,

I've just noticed that the implementation of quick sort in torch is not randomized. Since the complexity of quick sort can be O(n^2) if the list is already sorted (and this is a case that actually happens, otherwise I wouldn't have noticed...), the sort function can become extremely slow.

I have a sample code :

require 'sys'

n = 100000

a = torch.linspace(1,n,n)

b = torch.randperm(n)

sys.tic()

b:sort()

print("random list : "..sys.toc().." seconds.")

a:sort()

print("sorted list : "..sys.toc().." seconds.")

Which outputs :

random list : 0.01768599999923 seconds.

sorted list : 3.8866019999987 seconds.

Four seconds to sort 100 thousands elements is simply ridiculous.

I wonder why the sorting function re-implements a quick sort instead of using C/C++ standard functions, namely qsort/sort .

Best,

Michael