CODEWITHSUNDEEP
pythonnumpysortingscipyinsertion-sort
goh
goh

Reputation: 29511

insertion sort in numpy?

Is there a insertion sort somewhere in numpy? I require a argsort for my array but the builtin quick,merge and heap are not suitable for nearly sorted array.

Upvotes: 4

Views: 2671

Answers (2)

Robert Pollak
Robert Pollak

Reputation: 4165

From the numpy 1.17.0 release notes:

Timsort has been implemented and is now used in place of mergesort. [...] Timsort features improved performace on already or nearly sorted data and performs like mergesort on random data.

As of the time of this writing, NumPy 1.17.0 is not out yet, but when it is, you will be able to select Timsort by specifying kind='stable' or kind='mergesort' in a sort call:

sorted = numpy.sort(unsorted, kind='stable')

This satisfies the "fast on nearly-sorted data" role you wanted to use insertion sort for, while also taking advantage of other order in the input and having much better worst-case behavior than insertion sort.

Earlier numpy versions do not have a fast method for nearly sorted data.

Upvotes: 3

JoshAdel
JoshAdel

Reputation: 68682

How about using numpy.searchsorted in conjunction with numpy.insert:

http://docs.scipy.org/doc/numpy/reference/generated/numpy.searchsorted.html

http://docs.scipy.org/doc/numpy/reference/generated/numpy.insert.html

Upvotes: 2

Related Questions