- A+

I tried to do a test, regarding `Collection.sort()`

and `Arrays.sort()`

. In the test, I created an array of `int`

s 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[])`

.

`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".- 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.