Why is Collections.sort() much slower than Arrays.sort()?

  • A+
Category:Languages

I tried to do a test, regarding Collection.sort() and Arrays.sort(). In the test, I created an array of ints of length 1e5 100 times, which contained random numbers from 1 to 1e5. I also created a list of type Integer, which contained the same values at the same positions as that of the array. Then I sorted the array using Arrays.sort() and the list using Collections.sort().

Here is the code:

import java.util.* ;   class TestClass {     public static void main(String args[] ) throws Exception {         double ratSum = 0 ;         for(int j=0;j<100;j++)         {         int[] A = new int[(int)1e5] ;         List<Integer> L = new ArrayList<Integer>() ;         for(int i=0;i<A.length;i++)         {             int no = (int)Math.random()*(int)1e5 ;             A[i] = no ;             L.add(A[i]) ;         }         long startTime = System.nanoTime() ;         Arrays.sort(A) ;         long endTime = System.nanoTime() ;         Collections.sort(L) ;         long endTime2 = System.nanoTime() ;         long t1 = (endTime-startTime), t2 = (endTime2-endTime) ;         ratSum+=(double)t2/t1 ;         System.out.println("Arrays.sort took :"+t1+" Collections.sort took :"+t2+" ratio :"+((double)t2/t1)) ;     }     System.out.println("Average ratio :"+(ratSum/100)) ;     } } 

The output was:

Arrays.sort took :3201267 Collections.sort took :6868229 ratio :2.1454720896445063 Arrays.sort took :917056 Collections.sort took :2012758 ratio :2.1948038069648965 Arrays.sort took :978908 Collections.sort took :1993531 ratio :2.0364845317435347 Arrays.sort took :890039 Collections.sort took :806900 ratio :0.9065894865281184 Arrays.sort took :210749 Collections.sort took :519196 ratio :2.4635751533815107 Arrays.sort took :214238 Collections.sort took :537204 ratio :2.5075103389688103 Arrays.sort took :217024 Collections.sort took :233526 ratio :1.0760376732527277 Arrays.sort took :215743 Collections.sort took :224973 ratio :1.0427823845964874 Arrays.sort took :215692 Collections.sort took :223778 ratio :1.0374886412106152 Arrays.sort took :222939 Collections.sort took :246313 ratio :1.1048448230233383 Arrays.sort took :214511 Collections.sort took :241628 ratio :1.1264130976966216 Arrays.sort took :212882 Collections.sort took :228729 ratio :1.074440300260238 Arrays.sort took :217570 Collections.sort took :226959 ratio :1.0431539274716184 Arrays.sort took :218142 Collections.sort took :229791 ratio :1.0534009956817119 Arrays.sort took :216271 Collections.sort took :229805 ratio :1.0625788940727143 Arrays.sort took :199298 Collections.sort took :235251 ratio :1.1803981976738351 Arrays.sort took :214368 Collections.sort took :240676 ratio :1.122723540826989 Arrays.sort took :218029 Collections.sort took :233281 ratio :1.0699539969453604 Arrays.sort took :217310 Collections.sort took :232489 ratio :1.069849523721872 Arrays.sort took :41578 Collections.sort took :127103 ratio :3.0569772475828563 Arrays.sort took :29015 Collections.sort took :125236 ratio :4.316250215405825 Arrays.sort took :28029 Collections.sort took :134302 ratio :4.791537336330229 Arrays.sort took :27979 Collections.sort took :124651 ratio :4.455162800671933 Arrays.sort took :28351 Collections.sort took :124582 ratio :4.394271806990935 Arrays.sort took :27803 Collections.sort took :124869 ratio :4.491205984965651 Arrays.sort took :28105 Collections.sort took :124488 ratio :4.429389788293898 Arrays.sort took :28217 Collections.sort took :124584 ratio :4.4152106885919835 Arrays.sort took :27231 Collections.sort took :125490 ratio :4.608350776688333 Arrays.sort took :27966 Collections.sort took :125397 ratio :4.483909032396482 Arrays.sort took :28453 Collections.sort took :124669 ratio :4.381576635152708 Arrays.sort took :28444 Collections.sort took :124850 ratio :4.389326395724933 Arrays.sort took :36872 Collections.sort took :126782 ratio :3.4384356693425904 Arrays.sort took :28962 Collections.sort took :124815 ratio :4.3096125958152065 Arrays.sort took :28748 Collections.sort took :125219 ratio :4.355746486712119 Arrays.sort took :29457 Collections.sort took :126645 ratio :4.299317649455138 Arrays.sort took :27755 Collections.sort took :126229 ratio :4.547973338137273 Arrays.sort took :28251 Collections.sort took :124773 ratio :4.416587023468196 Arrays.sort took :29021 Collections.sort took :124890 ratio :4.30343544329968 Arrays.sort took :28600 Collections.sort took :124788 ratio :4.363216783216783 Arrays.sort took :31109 Collections.sort took :127335 ratio :4.093188466360218 Arrays.sort took :27516 Collections.sort took :124867 ratio :4.537977903765082 Arrays.sort took :28450 Collections.sort took :124649 ratio :4.3813356766256595 Arrays.sort took :28949 Collections.sort took :126513 ratio :4.370202770389305 Arrays.sort took :28251 Collections.sort took :124947 ratio :4.422746097483275 Arrays.sort took :28558 Collections.sort took :124810 ratio :4.370404089922263 Arrays.sort took :28295 Collections.sort took :124994 ratio :4.417529598869058 Arrays.sort took :41832 Collections.sort took :132124 ratio :3.158443296997514 Arrays.sort took :27979 Collections.sort took :126849 ratio :4.533721719861324 Arrays.sort took :28763 Collections.sort took :124752 ratio :4.337238813753781 Arrays.sort took :27067 Collections.sort took :124827 ratio :4.611778180071674 Arrays.sort took :28870 Collections.sort took :124721 ratio :4.320090058884655 Arrays.sort took :28580 Collections.sort took :124714 ratio :4.363680895731281 Arrays.sort took :29195 Collections.sort took :127176 ratio :4.356088371296455 Arrays.sort took :28907 Collections.sort took :124972 ratio :4.323243505033383 Arrays.sort took :30923 Collections.sort took :125649 ratio :4.063286227080167 Arrays.sort took :28639 Collections.sort took :124763 ratio :4.356402109012186 Arrays.sort took :28694 Collections.sort took :124982 ratio :4.3556841151460235 Arrays.sort took :29265 Collections.sort took :124696 ratio :4.260926020844011 Arrays.sort took :27907 Collections.sort took :124829 ratio :4.473035439137134 Arrays.sort took :29009 Collections.sort took :124529 ratio :4.292771208935158 Arrays.sort took :28469 Collections.sort took :124632 ratio :4.3778144648565105 Arrays.sort took :28826 Collections.sort took :138589 ratio :4.80777770068688 Arrays.sort took :26033 Collections.sort took :126018 ratio :4.840702185687396 Arrays.sort took :33395 Collections.sort took :126899 ratio :3.799940110795029 Arrays.sort took :41084 Collections.sort took :132857 ratio :3.2337893097069417 Arrays.sort took :29060 Collections.sort took :126081 ratio :4.3386441844459736 Arrays.sort took :27856 Collections.sort took :125442 ratio :4.503230901780586 Arrays.sort took :28300 Collections.sort took :124783 ratio :4.409293286219081 Arrays.sort took :29345 Collections.sort took :125066 ratio :4.261918555120123 Arrays.sort took :29063 Collections.sort took :130896 ratio :4.5038709011457865 Arrays.sort took :29060 Collections.sort took :125711 ratio :4.325911906400551 Arrays.sort took :28158 Collections.sort took :124449 ratio :4.419667590027701 Arrays.sort took :29106 Collections.sort took :124973 ratio :4.293719508005222 Arrays.sort took :29163 Collections.sort took :124919 ratio :4.283475636937215 Arrays.sort took :28401 Collections.sort took :124904 ratio :4.397873314319918 Arrays.sort took :27397 Collections.sort took :124804 ratio :4.555389276198124 Arrays.sort took :28396 Collections.sort took :124592 ratio :4.387660233835751 Arrays.sort took :28948 Collections.sort took :124512 ratio :4.301229791350007 Arrays.sort took :29034 Collections.sort took :125484 ratio :4.3219673486257495 Arrays.sort took :30021 Collections.sort took :127120 ratio :4.234369274840945 Arrays.sort took :27591 Collections.sort took :124957 ratio :4.528904352868689 Arrays.sort took :28793 Collections.sort took :124504 ratio :4.32410655367624 Arrays.sort took :28917 Collections.sort took :124553 ratio :4.307258705951517 Arrays.sort took :29168 Collections.sort took :126438 ratio :4.334818979703785 Arrays.sort took :29719 Collections.sort took :140453 ratio :4.726033850398735 Arrays.sort took :29396 Collections.sort took :130836 ratio :4.450809633963805 Arrays.sort took :29399 Collections.sort took :126519 ratio :4.303513724956631 Arrays.sort took :28467 Collections.sort took :125312 ratio :4.402009344152879 Arrays.sort took :28568 Collections.sort took :124572 ratio :4.360543265191823 Arrays.sort took :28788 Collections.sort took :125462 ratio :4.358135334167014 Arrays.sort took :29081 Collections.sort took :124601 ratio :4.284618823286682 Arrays.sort took :28472 Collections.sort took :137346 ratio :4.823897162124192 Arrays.sort took :28307 Collections.sort took :124439 ratio :4.396050446885929 Arrays.sort took :28341 Collections.sort took :124437 ratio :4.390706044246851 Arrays.sort took :27909 Collections.sort took :124773 ratio :4.4707083736429105 Arrays.sort took :32930 Collections.sort took :125352 ratio :3.8066201032493168 Arrays.sort took :29267 Collections.sort took :125621 ratio :4.292240407284655 Arrays.sort took :29311 Collections.sort took :125263 ratio :4.273583296373375 Arrays.sort took :28536 Collections.sort took :148872 ratio :5.216989066442388 Arrays.sort took :28647 Collections.sort took :124803 ratio :4.356581841030474 Average ratio :3.779721444576913 

The code can be run here. Why does Collections.sort() take 3.7 times of the time taken by Arrays.sort() to sort the same values? Is it because now we're not comparing primitives? Why would that take more time?

 


So, there are two different methods with totally different algorithms here:

Arrays.sort(int[]) uses a dual-pivot quicksort algorithm.

Collections.sort(List<T>) calls list.sort(null) which in turn calls Arrays.sort(T[]). This uses a Timsort algorithm.

So, let's compare Arrays.sort(int[]) and Arrays.sort(T[]).

  1. T[] is a boxed array so there is one extra level of indirection: for each call, you have to unwrap Integer. This certainly leads to an overhead. On the other hand, int[] is a primitive array so all elements are available "immediately".
  2. TimSort is a variation of a classic mergesort algorithm. It is faster than mergesort but it still slower than quicksort because: a) quicksort has fewer data movements on random data b) quicksort requires O(log(n)) extra space while TimSort requires O(n) to provide stability which also leads to an overhead.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: