Sorting a List in parallel without creating a temporary array in Java 8

by

There doesn’t appear to be any straightforward way to sort a List in parallel in Java 8. I don’t think this is fundamentally difficult; it looks more like an oversight to me.

The difficulty with a hypothetical Collections.parallelSort(list, cmp) is that the Collections implementation knows nothing about the list’s implementation or its internal organization. This can be seen by examining the Java 7 implementation of Collections.sort(list, cmp). As you observed, it has to copy the list elements out to an array, sort them, and then copy them back into the list.

This is the big advantage of the List.sort(cmp) extension method over Collections.sort(list, cmp). It might seem that this is merely a small syntactic advantage being able to write myList.sort(cmp) instead of Collections.sort(myList, cmp). The difference is that myList.sort(cmp), being an interface extension method, can be overridden by the specific List implementation. For example, ArrayList.sort(cmp) sorts the list in-place using Arrays.sort() whereas the default implementation implements the old copyout-sort-copyback technique.

It should be possible to add a parallelSort extension method to the List interface that has similar semantics to List.sort but does the sorting in parallel. This would allow ArrayList to do a straightforward in-place sort using Arrays.parallelSort. (It’s not entirely clear to me what the default implementation should do. It might still be worth it to do copyout-parallelSort-copyback.) Since this would be an API change, it can’t happen until the next major release of Java SE.

As for a Java 8 solution, there are a couple workarounds, none very pretty (as is typical of workarounds). You could create your own array-based List implementation and override sort() to sort in parallel. Or you could subclass ArrayList, override sort(), grab the elementData array via reflection and call parallelSort() on it. Of course you could just write your own List implementation and provide a parallelSort() method, but the advantage of overriding List.sort() is that this works on the plain List interface and you don’t have to modify all the code in your code base to use a different List subclass.

More Related Contents:

  1. Very confused by Java 8 Comparator type inference
  2. Java 8 stream reverse order
  3. Reverse a comparator in Java 8
  4. Why does Collections.sort use Mergesort but Arrays.sort does not?
  5. Java8 Collections.sort (sometimes) does not sort JPA returned lists
  6. java: Arrays.sort() with lambda expression
  7. Difference between Arrays.sort() and Arrays.parallelSort()
  8. Group sequences of values
  9. Write a function that will sort a string array using Java
  10. Sort ArrayList of custom Objects by property
  11. How to sort an array of objects in Java?
  12. Is method reference caching a good idea in Java 8?
  13. Java 8: Lambda-Streams, Filter by Method with Exception
  14. How to convert a Java 8 Stream to an Array?
  15. In Java 8, is there a ByteStream class?
  16. Sum values from specific field of the objects in a list
  17. How do I define a method which takes a lambda as a parameter in Java 8?
  18. What’s the difference between instance method reference types in Java 8?
  19. Formatting a Duration in Java 8 / jsr310
  20. Most efficient way to get the last element of a stream
  21. Why does findFirst() throw a NullPointerException if the first element it finds is null?
  22. Java 8 Stream IllegalStateException: Stream has already been operated on or closed
  23. Java Sort List of Lists
  24. Why can we use ‘this’ as an instance method parameter?
  25. When and why would you use Java’s Supplier and Consumer interfaces?
  26. What’s the difference of dual pivot quick sort and quick sort?
  27. Implied anonymous types inside lambdas
  28. How to specify function types for void (not Void) methods in Java8?
  29. Adding two Java 8 streams, or an extra element to a stream
  30. Built-in Java 8 predicate that always returns true?

Leave a Comment