Fastest way to get a sorted array out of an Iterable of integers

Question

Possible Duplicate:
Fastest strategy to form and sort an array of positive integers

What would be the fastest way to get a sorted array from an unsorted iterable of integers ? Currently I do it by iterating over the iterable n no of times (where n is size of list) each time getting the highest from iterable & putting it in array. But I'm looking to clean this up & let some good library do it for me.

Probably I won't mind using any popular libraries like Guava, etc for this purpose.

Would populating then sorting not be fast enough? Related: http://stackoverflow.com/questions/12063849/fastest-strategy-to-form-and-sort-an-array-of-positive-integers?rq=1 — assylias, Nov 02 '12 at 13:05
Collection.sort uses [Timsort](http://en.wikipedia.org/wiki/Timsort) that is fastest sorting algo on this earth and has been incorporated since JDK 7 — AurA, Nov 02 '12 at 13:08
@CAMOBAP: Collections.sort() cannot be used for Iterables, I guess. — Rajat Gupta, Nov 02 '12 at 13:08
My guess, without timing tests, would be Arrays.sort(Ints.toArray(ImmutableList.copyOf(iterable))). This will quickly unbox the Integers to ints, where sorting can be more efficient. IIRC, Comparables are sorted with TimSort, and primatives are sorted with a two-pivot quicksort. — Robert Cooper, Nov 02 '12 at 13:13
@AurA TimSort isn't the fastest sorting algorithm on earth, but it's the fastest stable sorting algorithm I know of. I believe that quicksorts are often faster, but can alter the order of equal values. — Robert Cooper, Nov 02 '12 at 13:20
I think the best way for me, right now, is first populate array then sort as suggested by @assylias, so I think I would go that way. Collections.sort() cannot be used with iterables, as per my understanding. — Rajat Gupta, Nov 02 '12 at 13:28
I know this isn't exactly an answer, but everyone should check out: http://www.sorting-algorithms.com/ — Patrick James McDougle, Nov 02 '12 at 13:34
`Ordering.natural().sortedCopy(integers)` does the job just fine. — Louis Wasserman, Nov 02 '12 at 17:06
I don't think that the marked as duplicate question is essentially the same. @LouisWasserman I believe you should post it as an answer, which should be accepted (sorry for posting after 5 years). I used this to sort the values of a spark pair rdd. — vefthym, Feb 21 '17 at 15:03

score 7 · Answer 1 · answered Nov 02 '12 at 14:32

It is essentially the same answer as assylias has already provided, but if you have Google Guava on the classpath, you can shorten it to :

import java.util.Collections;
import java.util.List;

import com.google.common.collect.Lists;

...

List list = Lists.newArrayList(iterable);
Collections.sort(list);

score 1 · Accepted Answer · answered Nov 02 '12 at 13:56

1

As commented, the easiest and probably fastest way is to populate a collection and sort it - I would simply use an ArrayList in this case:

List<Integer> sortedList = new ArrayList<>();
for (Integer i : yourIterable) {
    sortedList.add(i);
}
Collections.sort(sortedList);

If you know the size of your Iterable beforehand you can initialise the arraylist with the right size to make an additional efficiency gain:

List<Integer> sortedList = new ArrayList<>(size);

answered Nov 02 '12 at 13:56

assylias

321,522
82
660
783

Thanks for providing it as an answer.. instead of using a list shouldn't I just use the int[] instead, if I know size? – Rajat Gupta Nov 02 '12 at 18:14
@user01 Not sure which would be faster. Sorting an array of `int[]` is probably slightly faster than sorting a `List`, but creating the array will require unboxing all the integers whereas creating the list will simply copy the references. You should test both approach and decide. If you do, make sure you read [how to write a micro benchmark](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). – assylias Nov 02 '12 at 18:19

Fastest way to get a sorted array out of an Iterable of integers

2 Answers2

Linked