Index: trunk/src/org/openstreetmap/josm/data/osm/visitor/paint/StyledMapRenderer.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/visitor/paint/StyledMapRenderer.java	(revision 12006)
+++ trunk/src/org/openstreetmap/josm/data/osm/visitor/paint/StyledMapRenderer.java	(revision 12009)
@@ -27,6 +27,6 @@
 import java.awt.image.BufferedImage;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collection;
-import java.util.Collections;
 import java.util.HashMap;
 import java.util.Iterator;
@@ -1523,5 +1523,7 @@
             }
 
-            Collections.sort(allStyleElems); // TODO: try parallel sort when switching to Java 8
+            // We use parallel sort here. This is only available for arrays.
+            StyleRecord[] sorted = allStyleElems.toArray(new StyleRecord[allStyleElems.size()]);
+            Arrays.parallelSort(sorted, null);
 
             if (!benchmark.renderDraw(allStyleElems)) {
@@ -1529,5 +1531,5 @@
             }
 
-            for (StyleRecord record : allStyleElems) {
+            for (StyleRecord record : sorted) {
                 paintRecord(record);
             }