CODEWITHSUNDEEP
javasortingcollections
RokL
RokL

Reputation: 2812

Fastest sort for small collections

Many times I have to sort large amounts of small lists, arrays. It is quite rare that I need to sort large arrays. Which is the fastest sort algorithm for sorting:

of size 8-15 elements of these types:

?

I am listing element types because some algorithms do more compare operations and less swap operations.

I am considering Merge Sort, Quick Sort, Insertion Sort and Shell sort (2^k - 1 increment).

Upvotes: 2

Views: 2049

Answers (3)

Stephen C
Stephen C

Reputation: 719709

Actually, there isn't a universal answer. Among other things, the performance of a Java sort algorithm will depend on the relative cost of the compare operation, and (for some algorithms) on the order of the input. In the case of a list, it also depends on the list implementation type.

But @Bozho's advice is sound, as is @Sean Patrick Floyd's comment.

FOLLOWUP

If you believe that the performance difference is going to be significant for your use-case, then you should get hold of some implementations of different algorithms, and test them out using the actual data that your application needs to deal with. (And if you don't have the data yet, it is too soon to start tuning your application, because the sort performance will depend on actual data.)

In short, you'll need to do the benchmarking yourself.

Upvotes: 1

Bozho
Bozho

Reputation: 597422

Arrays.sort(..) / Collections.sort(..) will make that decision for you.

For example, the openjdk-7 implementation of Arrays.sort(..) has INSERTION_SORT_THRESHOLD = 47 - it uses insertion sort for those with less than 47 elements.

Upvotes: 13

Jim
Jim

Reputation: 22656

Unless you can prove that this is a bottleneck then the built in sorts are fine:

Collections.sort(myIntList);

Arrays.sort(myArray);

Upvotes: 1

Related Questions