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

Clash Royale CLAN TAG#URR8PPP

up vote
11
down vote

favorite

3

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?

java arrays list sorting timing

share|improve this question

edited 8 mins ago

Stefan Steinegger

53.3k13106177

asked 48 mins ago

Mooncrater

637820

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Collections.sort() has overheads, because Integer is class( additional operations are there), where as Arrays.sort() , it has reduced operation as the elemetns are int primitive .
  – The Scientific Method
  44 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @TheScientificMethod Overheads are inferable from the extra running time. But exactly which ones do this? What exactly slows Collections.sort() down?
  – Mooncrater
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  stackoverflow.com/questions/32334319/…
  – Vivek Swansi
  24 mins ago
  

  
  
  
  

add a comment | 

up vote
11
down vote

favorite

3

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?

java arrays list sorting timing

share|improve this question

edited 8 mins ago

Stefan Steinegger

53.3k13106177

asked 48 mins ago

Mooncrater

637820

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Collections.sort() has overheads, because Integer is class( additional operations are there), where as Arrays.sort() , it has reduced operation as the elemetns are int primitive .
  – The Scientific Method
  44 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @TheScientificMethod Overheads are inferable from the extra running time. But exactly which ones do this? What exactly slows Collections.sort() down?
  – Mooncrater
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  stackoverflow.com/questions/32334319/…
  – Vivek Swansi
  24 mins ago
  

  
  
  
  

add a comment | 

up vote
11
down vote

favorite

3

up vote
11
down vote

favorite

3

3

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?

java arrays list sorting timing

share|improve this question

edited 8 mins ago

Stefan Steinegger

53.3k13106177

asked 48 mins ago

Mooncrater

637820

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?

java arrays list sorting timing

java arrays list sorting timing

share|improve this question

edited 8 mins ago

Stefan Steinegger

53.3k13106177

asked 48 mins ago

Mooncrater

637820

share|improve this question

edited 8 mins ago

Stefan Steinegger

53.3k13106177

asked 48 mins ago

Mooncrater

637820

share|improve this question

share|improve this question

edited 8 mins ago

Stefan Steinegger

53.3k13106177

edited 8 mins ago

Stefan Steinegger

53.3k13106177

edited 8 mins ago

Stefan Steinegger

53.3k13106177

53.3k13106177

asked 48 mins ago

Mooncrater

637820

asked 48 mins ago

Mooncrater

637820

asked 48 mins ago

Mooncrater

637820

637820

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Collections.sort() has overheads, because Integer is class( additional operations are there), where as Arrays.sort() , it has reduced operation as the elemetns are int primitive .
  – The Scientific Method
  44 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @TheScientificMethod Overheads are inferable from the extra running time. But exactly which ones do this? What exactly slows Collections.sort() down?
  – Mooncrater
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  stackoverflow.com/questions/32334319/…
  – Vivek Swansi
  24 mins ago
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Collections.sort() has overheads, because Integer is class( additional operations are there), where as Arrays.sort() , it has reduced operation as the elemetns are int primitive .
  – The Scientific Method
  44 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @TheScientificMethod Overheads are inferable from the extra running time. But exactly which ones do this? What exactly slows Collections.sort() down?
  – Mooncrater
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  stackoverflow.com/questions/32334319/…
  – Vivek Swansi
  24 mins ago
  

  
  
  
  

Collections.sort() has overheads, because Integer is class( additional operations are there), where as Arrays.sort() , it has reduced operation as the elemetns are int primitive .
– The Scientific Method
44 mins ago

Collections.sort() has overheads, because Integer is class( additional operations are there), where as Arrays.sort() , it has reduced operation as the elemetns are int primitive .
– The Scientific Method
44 mins ago

@TheScientificMethod Overheads are inferable from the extra running time. But exactly which ones do this? What exactly slows Collections.sort() down?
– Mooncrater
33 mins ago

@TheScientificMethod Overheads are inferable from the extra running time. But exactly which ones do this? What exactly slows Collections.sort() down?
– Mooncrater
33 mins ago

stackoverflow.com/questions/32334319/…
– Vivek Swansi
24 mins ago

stackoverflow.com/questions/32334319/…
– Vivek Swansi
24 mins ago

add a comment | 

6 Answers
6

active

oldest

votes

up vote
10
down vote

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(1) extra space while TimSort requires O(n) to provide stability which also leads to an overhead.

share|improve this answer

answered 20 mins ago

ZhekaKozlov

13.3k758103

add a comment | 

up vote
1
down vote

Collection.sort() used Merge sort algorithm and Arrays.sort() uses quick sort.
Quick Sort has major drawbacks when it comes to merge sort, it's not stable while it comes to non primitive.
So depends on requirement we will be using either Arrays.sort() or Collection.sort() weather need to compare objects or primitives.

share|improve this answer

answered 17 mins ago

John

45110

add a comment | 

up vote
1
down vote

Besides the algorithm is different (Quicksort for Arrays.sort & Timsort for Collections.sort) another difference I noticed when I saw the implementation of the Collections.sort is:

Collections.sort = Arrays.sort to sort ((O(NlogN))) + Additional iterations to copy back ((O(N)))

Online sourcecode for the Collections.sort implementation leads to below:
https://zgrepcode.com/java/oracle/jdk-8u181/java/util/collections.java#L-139

Screenshot:

share|improve this answer

edited 2 mins ago

answered 18 mins ago

Parth

5,25042550

add a comment | 

up vote
1
down vote

There are two issues here:

Issue #1:

Under the covers, Collections.sort works by copying the collection to an array, sorting the array, then copying the array back to the collection.

Arrays.sort just sorts the array in place.

Now for a large enough array / collection, the cost of sorting (O(NlogN)) will dominate the cost of copying (O(N)). For a small array / collection, the copying becomes significant.

(This behavior may depend on the collection type. For an ArrayList, the Collections.sort implementation may be able to sort the backing array without copying data. I would need to check the source code .....)

Issue #2:

You are comparing sorting an int with sorting a List<Integer>.

This is apples and oranges. Because:

1. Comparing two int values using relational operators is faster than comparing two Integer values using compareTo(Object).


2. 
   Arrays.sort(int) uses a different (faster) algorithm to the one used by Arrays.sort(Object)
   

If you want a fairer comparison, compare Collections.sort on an ArrayList<Integer> with Arrays.sort(Object) on a Integer.

share|improve this answer

edited 1 min ago

answered 13 mins ago

Stephen C

501k68549898

add a comment | 

up vote
0
down vote

It's only because of unboxing the Integer.

Change the int to Integer, it produces on my machine:

Arrays.sort took :1644305 Collections.sort took :791381 ratio :0.4812860144559555
Arrays.sort took :463652 Collections.sort took :476490 ratio :1.0276888701008515
Arrays.sort took :445529 Collections.sort took :476490 ratio :1.0694926705107861
Arrays.sort took :505184 Collections.sort took :445152 ratio :0.8811680496611136
Arrays.sort took :444775 Collections.sort took :501031 ratio :1.1264819290652577
Arrays.sort took :505185 Collections.sort took :827250 ratio :1.6375189287092846
Arrays.sort took :483286 Collections.sort took :490837 ratio :1.0156242887234475
Arrays.sort took :480265 Collections.sort took :444019 ratio :0.9245291661894995
Arrays.sort took :445152 Collections.sort took :494613 ratio :1.1111103623032133
Arrays.sort took :486306 Collections.sort took :430427 ratio :0.8850949813491916
Arrays.sort took :447417 Collections.sort took :467806 ratio :1.0455704633485092
Arrays.sort took :675468 Collections.sort took :499899 ratio :0.7400779903711204
Arrays.sort took :475357 Collections.sort took :431560 ratio :0.9078650361728132
Arrays.sort took :434203 Collections.sort took :431937 ratio :0.9947812428748765
Arrays.sort took :485174 Collections.sort took :445907 ratio :0.9190661494639036
Arrays.sort took :559177 Collections.sort took :559932 ratio :1.0013501985954358
Arrays.sort took :434203 Collections.sort took :518399 ratio :1.193909300488481
Arrays.sort took :477623 Collections.sort took :445907 ratio :0.9335961626638584
Arrays.sort took :483664 Collections.sort took :444774 ratio :0.9195929405537728

While int on my box produces:

Arrays.sort took :8636850 Collections.sort took :1895765 ratio :0.219497270416876
Arrays.sort took :257123 Collections.sort took :1219542 ratio :4.743029600619159
Arrays.sort took :135924 Collections.sort took :564463 ratio :4.152783908654836
Arrays.sort took :131771 Collections.sort took :558044 ratio :4.234953062509961
Arrays.sort took :124975 Collections.sort took :484418 ratio :3.876119223844769
Arrays.sort took :124220 Collections.sort took :445907 ratio :3.5896554500080504
Arrays.sort took :126107 Collections.sort took :485929 ratio :3.853307112214231
Arrays.sort took :125353 Collections.sort took :525196 ratio :4.189736185013522
Arrays.sort took :168017 Collections.sort took :448173 ratio :2.667426510412637
Arrays.sort took :124975 Collections.sort took :446285 ratio :3.570994198839768
Arrays.sort took :159334 Collections.sort took :447039 ratio :2.8056723612035097
Arrays.sort took :131394 Collections.sort took :448172 ratio :3.4109015632372865
Arrays.sort took :125352 Collections.sort took :446662 ratio :3.5632618546173975
Arrays.sort took :176324 Collections.sort took :522175 ratio :2.961451645833806
Arrays.sort took :125730 Collections.sort took :475735 ratio :3.7837827089795595
Arrays.sort took :124597 Collections.sort took :446285 ratio :3.5818278128686885
Arrays.sort took :125353 Collections.sort took :446662 ratio :3.5632334287970773
Arrays.sort took :147251 Collections.sort took :464408 ratio :3.1538529449715114
Arrays.sort took :168395 Collections.sort took :447417 ratio :2.6569494343656284
Arrays.sort took :243153 Collections.sort took :642242 ratio :2.6413081475449616
Arrays.sort took :129128 Collections.sort took :460254 ratio :3.564323771761353
Arrays.sort took :253348 Collections.sort took :474602 ratio :1.8733204919715174

share|improve this answer

answered 13 mins ago

Stefan Steinegger

53.3k13106177

add a comment | 

up vote
0
down vote

if you see Collections.sort() docs it reads

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array

which means it is doing array sort and additional iteration, this implies Collections.sort() is slower than arrays.sort

1. dumps the specified list into an array


2. sorts the array ~ arrays.sort


3. iterates over the list resetting each element from the corresponding position in the array

share|improve this answer

edited 5 mins ago

answered 12 mins ago

The Scientific Method

1,231412

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52714131%2fwhy-is-collections-sort-much-slower-than-arrays-sort%23new-answer', 'question_page');

);

Post as a guest

Name Email

6 Answers
6

active

oldest

votes

6 Answers
6

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
10
down vote

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(1) extra space while TimSort requires O(n) to provide stability which also leads to an overhead.

share|improve this answer

answered 20 mins ago

ZhekaKozlov

13.3k758103

add a comment | 

up vote
10
down vote

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(1) extra space while TimSort requires O(n) to provide stability which also leads to an overhead.

share|improve this answer

answered 20 mins ago

ZhekaKozlov

13.3k758103

add a comment | 

up vote
10
down vote

up vote
10
down vote

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(1) extra space while TimSort requires O(n) to provide stability which also leads to an overhead.

share|improve this answer

answered 20 mins ago

ZhekaKozlov

13.3k758103

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(1) extra space while TimSort requires O(n) to provide stability which also leads to an overhead.

share|improve this answer

answered 20 mins ago

ZhekaKozlov

13.3k758103

share|improve this answer

share|improve this answer

answered 20 mins ago

ZhekaKozlov

13.3k758103

answered 20 mins ago

ZhekaKozlov

13.3k758103

answered 20 mins ago

ZhekaKozlov

13.3k758103

13.3k758103

add a comment | 

add a comment | 

up vote
1
down vote

Collection.sort() used Merge sort algorithm and Arrays.sort() uses quick sort.
Quick Sort has major drawbacks when it comes to merge sort, it's not stable while it comes to non primitive.
So depends on requirement we will be using either Arrays.sort() or Collection.sort() weather need to compare objects or primitives.

share|improve this answer

answered 17 mins ago

John

45110

add a comment | 

up vote
1
down vote

Collection.sort() used Merge sort algorithm and Arrays.sort() uses quick sort.
Quick Sort has major drawbacks when it comes to merge sort, it's not stable while it comes to non primitive.
So depends on requirement we will be using either Arrays.sort() or Collection.sort() weather need to compare objects or primitives.

share|improve this answer

answered 17 mins ago

John

45110

add a comment | 

up vote
1
down vote

up vote
1
down vote

Collection.sort() used Merge sort algorithm and Arrays.sort() uses quick sort.
Quick Sort has major drawbacks when it comes to merge sort, it's not stable while it comes to non primitive.
So depends on requirement we will be using either Arrays.sort() or Collection.sort() weather need to compare objects or primitives.

share|improve this answer

answered 17 mins ago

John

45110

Collection.sort() used Merge sort algorithm and Arrays.sort() uses quick sort.
Quick Sort has major drawbacks when it comes to merge sort, it's not stable while it comes to non primitive.
So depends on requirement we will be using either Arrays.sort() or Collection.sort() weather need to compare objects or primitives.

share|improve this answer

answered 17 mins ago

John

45110

share|improve this answer

share|improve this answer

answered 17 mins ago

John

45110

answered 17 mins ago

John

45110

answered 17 mins ago

John

45110

45110

add a comment | 

add a comment | 

up vote
1
down vote

Besides the algorithm is different (Quicksort for Arrays.sort & Timsort for Collections.sort) another difference I noticed when I saw the implementation of the Collections.sort is:

Collections.sort = Arrays.sort to sort ((O(NlogN))) + Additional iterations to copy back ((O(N)))

Online sourcecode for the Collections.sort implementation leads to below:
https://zgrepcode.com/java/oracle/jdk-8u181/java/util/collections.java#L-139

Screenshot:

share|improve this answer

edited 2 mins ago

answered 18 mins ago

Parth

5,25042550

add a comment | 

up vote
1
down vote

Besides the algorithm is different (Quicksort for Arrays.sort & Timsort for Collections.sort) another difference I noticed when I saw the implementation of the Collections.sort is:

Collections.sort = Arrays.sort to sort ((O(NlogN))) + Additional iterations to copy back ((O(N)))

Online sourcecode for the Collections.sort implementation leads to below:
https://zgrepcode.com/java/oracle/jdk-8u181/java/util/collections.java#L-139

Screenshot:

share|improve this answer

edited 2 mins ago

answered 18 mins ago

Parth

5,25042550

add a comment | 

up vote
1
down vote

up vote
1
down vote

Besides the algorithm is different (Quicksort for Arrays.sort & Timsort for Collections.sort) another difference I noticed when I saw the implementation of the Collections.sort is:

Collections.sort = Arrays.sort to sort ((O(NlogN))) + Additional iterations to copy back ((O(N)))

Online sourcecode for the Collections.sort implementation leads to below:
https://zgrepcode.com/java/oracle/jdk-8u181/java/util/collections.java#L-139

Screenshot:

share|improve this answer

edited 2 mins ago

answered 18 mins ago

Parth

5,25042550

Besides the algorithm is different (Quicksort for Arrays.sort & Timsort for Collections.sort) another difference I noticed when I saw the implementation of the Collections.sort is:

Collections.sort = Arrays.sort to sort ((O(NlogN))) + Additional iterations to copy back ((O(N)))

Online sourcecode for the Collections.sort implementation leads to below:
https://zgrepcode.com/java/oracle/jdk-8u181/java/util/collections.java#L-139

Screenshot:

share|improve this answer

edited 2 mins ago

answered 18 mins ago

Parth

5,25042550

share|improve this answer

share|improve this answer

edited 2 mins ago

edited 2 mins ago

edited 2 mins ago

answered 18 mins ago

Parth

5,25042550

answered 18 mins ago

Parth

5,25042550

answered 18 mins ago

Parth

5,25042550

5,25042550

add a comment | 

add a comment | 

up vote
1
down vote

There are two issues here:

Issue #1:

Under the covers, Collections.sort works by copying the collection to an array, sorting the array, then copying the array back to the collection.

Arrays.sort just sorts the array in place.

Now for a large enough array / collection, the cost of sorting (O(NlogN)) will dominate the cost of copying (O(N)). For a small array / collection, the copying becomes significant.

(This behavior may depend on the collection type. For an ArrayList, the Collections.sort implementation may be able to sort the backing array without copying data. I would need to check the source code .....)

Issue #2:

You are comparing sorting an int with sorting a List<Integer>.

This is apples and oranges. Because:

1. Comparing two int values using relational operators is faster than comparing two Integer values using compareTo(Object).


2. 
   Arrays.sort(int) uses a different (faster) algorithm to the one used by Arrays.sort(Object)
   

If you want a fairer comparison, compare Collections.sort on an ArrayList<Integer> with Arrays.sort(Object) on a Integer.

share|improve this answer

edited 1 min ago

answered 13 mins ago

Stephen C

501k68549898

add a comment | 

up vote
1
down vote

There are two issues here:

Issue #1:

Under the covers, Collections.sort works by copying the collection to an array, sorting the array, then copying the array back to the collection.

Arrays.sort just sorts the array in place.

Now for a large enough array / collection, the cost of sorting (O(NlogN)) will dominate the cost of copying (O(N)). For a small array / collection, the copying becomes significant.

(This behavior may depend on the collection type. For an ArrayList, the Collections.sort implementation may be able to sort the backing array without copying data. I would need to check the source code .....)

Issue #2:

You are comparing sorting an int with sorting a List<Integer>.

This is apples and oranges. Because:

1. Comparing two int values using relational operators is faster than comparing two Integer values using compareTo(Object).


2. 
   Arrays.sort(int) uses a different (faster) algorithm to the one used by Arrays.sort(Object)
   

If you want a fairer comparison, compare Collections.sort on an ArrayList<Integer> with Arrays.sort(Object) on a Integer.

share|improve this answer

edited 1 min ago

answered 13 mins ago

Stephen C

501k68549898

add a comment | 

up vote
1
down vote

up vote
1
down vote

There are two issues here:

Issue #1:

Under the covers, Collections.sort works by copying the collection to an array, sorting the array, then copying the array back to the collection.

Arrays.sort just sorts the array in place.

Now for a large enough array / collection, the cost of sorting (O(NlogN)) will dominate the cost of copying (O(N)). For a small array / collection, the copying becomes significant.

(This behavior may depend on the collection type. For an ArrayList, the Collections.sort implementation may be able to sort the backing array without copying data. I would need to check the source code .....)

Issue #2:

You are comparing sorting an int with sorting a List<Integer>.

This is apples and oranges. Because:

1. Comparing two int values using relational operators is faster than comparing two Integer values using compareTo(Object).


2. 
   Arrays.sort(int) uses a different (faster) algorithm to the one used by Arrays.sort(Object)
   

If you want a fairer comparison, compare Collections.sort on an ArrayList<Integer> with Arrays.sort(Object) on a Integer.

share|improve this answer

edited 1 min ago

answered 13 mins ago

Stephen C

501k68549898

There are two issues here:

Issue #1:

Under the covers, Collections.sort works by copying the collection to an array, sorting the array, then copying the array back to the collection.

Arrays.sort just sorts the array in place.

Now for a large enough array / collection, the cost of sorting (O(NlogN)) will dominate the cost of copying (O(N)). For a small array / collection, the copying becomes significant.

(This behavior may depend on the collection type. For an ArrayList, the Collections.sort implementation may be able to sort the backing array without copying data. I would need to check the source code .....)

Issue #2:

You are comparing sorting an int with sorting a List<Integer>.

This is apples and oranges. Because:

1. Comparing two int values using relational operators is faster than comparing two Integer values using compareTo(Object).


2. 
   Arrays.sort(int) uses a different (faster) algorithm to the one used by Arrays.sort(Object)
   

If you want a fairer comparison, compare Collections.sort on an ArrayList<Integer> with Arrays.sort(Object) on a Integer.

share|improve this answer

edited 1 min ago

answered 13 mins ago

Stephen C

501k68549898

share|improve this answer

share|improve this answer

edited 1 min ago

edited 1 min ago

edited 1 min ago

answered 13 mins ago

Stephen C

501k68549898

answered 13 mins ago

Stephen C

501k68549898

answered 13 mins ago

Stephen C

501k68549898

501k68549898

add a comment | 

add a comment | 

up vote
0
down vote

It's only because of unboxing the Integer.

Change the int to Integer, it produces on my machine:

Arrays.sort took :1644305 Collections.sort took :791381 ratio :0.4812860144559555
Arrays.sort took :463652 Collections.sort took :476490 ratio :1.0276888701008515
Arrays.sort took :445529 Collections.sort took :476490 ratio :1.0694926705107861
Arrays.sort took :505184 Collections.sort took :445152 ratio :0.8811680496611136
Arrays.sort took :444775 Collections.sort took :501031 ratio :1.1264819290652577
Arrays.sort took :505185 Collections.sort took :827250 ratio :1.6375189287092846
Arrays.sort took :483286 Collections.sort took :490837 ratio :1.0156242887234475
Arrays.sort took :480265 Collections.sort took :444019 ratio :0.9245291661894995
Arrays.sort took :445152 Collections.sort took :494613 ratio :1.1111103623032133
Arrays.sort took :486306 Collections.sort took :430427 ratio :0.8850949813491916
Arrays.sort took :447417 Collections.sort took :467806 ratio :1.0455704633485092
Arrays.sort took :675468 Collections.sort took :499899 ratio :0.7400779903711204
Arrays.sort took :475357 Collections.sort took :431560 ratio :0.9078650361728132
Arrays.sort took :434203 Collections.sort took :431937 ratio :0.9947812428748765
Arrays.sort took :485174 Collections.sort took :445907 ratio :0.9190661494639036
Arrays.sort took :559177 Collections.sort took :559932 ratio :1.0013501985954358
Arrays.sort took :434203 Collections.sort took :518399 ratio :1.193909300488481
Arrays.sort took :477623 Collections.sort took :445907 ratio :0.9335961626638584
Arrays.sort took :483664 Collections.sort took :444774 ratio :0.9195929405537728

While int on my box produces:

Arrays.sort took :8636850 Collections.sort took :1895765 ratio :0.219497270416876
Arrays.sort took :257123 Collections.sort took :1219542 ratio :4.743029600619159
Arrays.sort took :135924 Collections.sort took :564463 ratio :4.152783908654836
Arrays.sort took :131771 Collections.sort took :558044 ratio :4.234953062509961
Arrays.sort took :124975 Collections.sort took :484418 ratio :3.876119223844769
Arrays.sort took :124220 Collections.sort took :445907 ratio :3.5896554500080504
Arrays.sort took :126107 Collections.sort took :485929 ratio :3.853307112214231
Arrays.sort took :125353 Collections.sort took :525196 ratio :4.189736185013522
Arrays.sort took :168017 Collections.sort took :448173 ratio :2.667426510412637
Arrays.sort took :124975 Collections.sort took :446285 ratio :3.570994198839768
Arrays.sort took :159334 Collections.sort took :447039 ratio :2.8056723612035097
Arrays.sort took :131394 Collections.sort took :448172 ratio :3.4109015632372865
Arrays.sort took :125352 Collections.sort took :446662 ratio :3.5632618546173975
Arrays.sort took :176324 Collections.sort took :522175 ratio :2.961451645833806
Arrays.sort took :125730 Collections.sort took :475735 ratio :3.7837827089795595
Arrays.sort took :124597 Collections.sort took :446285 ratio :3.5818278128686885
Arrays.sort took :125353 Collections.sort took :446662 ratio :3.5632334287970773
Arrays.sort took :147251 Collections.sort took :464408 ratio :3.1538529449715114
Arrays.sort took :168395 Collections.sort took :447417 ratio :2.6569494343656284
Arrays.sort took :243153 Collections.sort took :642242 ratio :2.6413081475449616
Arrays.sort took :129128 Collections.sort took :460254 ratio :3.564323771761353
Arrays.sort took :253348 Collections.sort took :474602 ratio :1.8733204919715174

share|improve this answer

answered 13 mins ago

Stefan Steinegger

53.3k13106177

add a comment | 

up vote
0
down vote

It's only because of unboxing the Integer.

Change the int to Integer, it produces on my machine:

Arrays.sort took :1644305 Collections.sort took :791381 ratio :0.4812860144559555
Arrays.sort took :463652 Collections.sort took :476490 ratio :1.0276888701008515
Arrays.sort took :445529 Collections.sort took :476490 ratio :1.0694926705107861
Arrays.sort took :505184 Collections.sort took :445152 ratio :0.8811680496611136
Arrays.sort took :444775 Collections.sort took :501031 ratio :1.1264819290652577
Arrays.sort took :505185 Collections.sort took :827250 ratio :1.6375189287092846
Arrays.sort took :483286 Collections.sort took :490837 ratio :1.0156242887234475
Arrays.sort took :480265 Collections.sort took :444019 ratio :0.9245291661894995
Arrays.sort took :445152 Collections.sort took :494613 ratio :1.1111103623032133
Arrays.sort took :486306 Collections.sort took :430427 ratio :0.8850949813491916
Arrays.sort took :447417 Collections.sort took :467806 ratio :1.0455704633485092
Arrays.sort took :675468 Collections.sort took :499899 ratio :0.7400779903711204
Arrays.sort took :475357 Collections.sort took :431560 ratio :0.9078650361728132
Arrays.sort took :434203 Collections.sort took :431937 ratio :0.9947812428748765
Arrays.sort took :485174 Collections.sort took :445907 ratio :0.9190661494639036
Arrays.sort took :559177 Collections.sort took :559932 ratio :1.0013501985954358
Arrays.sort took :434203 Collections.sort took :518399 ratio :1.193909300488481
Arrays.sort took :477623 Collections.sort took :445907 ratio :0.9335961626638584
Arrays.sort took :483664 Collections.sort took :444774 ratio :0.9195929405537728

While int on my box produces:

Arrays.sort took :8636850 Collections.sort took :1895765 ratio :0.219497270416876
Arrays.sort took :257123 Collections.sort took :1219542 ratio :4.743029600619159
Arrays.sort took :135924 Collections.sort took :564463 ratio :4.152783908654836
Arrays.sort took :131771 Collections.sort took :558044 ratio :4.234953062509961
Arrays.sort took :124975 Collections.sort took :484418 ratio :3.876119223844769
Arrays.sort took :124220 Collections.sort took :445907 ratio :3.5896554500080504
Arrays.sort took :126107 Collections.sort took :485929 ratio :3.853307112214231
Arrays.sort took :125353 Collections.sort took :525196 ratio :4.189736185013522
Arrays.sort took :168017 Collections.sort took :448173 ratio :2.667426510412637
Arrays.sort took :124975 Collections.sort took :446285 ratio :3.570994198839768
Arrays.sort took :159334 Collections.sort took :447039 ratio :2.8056723612035097
Arrays.sort took :131394 Collections.sort took :448172 ratio :3.4109015632372865
Arrays.sort took :125352 Collections.sort took :446662 ratio :3.5632618546173975
Arrays.sort took :176324 Collections.sort took :522175 ratio :2.961451645833806
Arrays.sort took :125730 Collections.sort took :475735 ratio :3.7837827089795595
Arrays.sort took :124597 Collections.sort took :446285 ratio :3.5818278128686885
Arrays.sort took :125353 Collections.sort took :446662 ratio :3.5632334287970773
Arrays.sort took :147251 Collections.sort took :464408 ratio :3.1538529449715114
Arrays.sort took :168395 Collections.sort took :447417 ratio :2.6569494343656284
Arrays.sort took :243153 Collections.sort took :642242 ratio :2.6413081475449616
Arrays.sort took :129128 Collections.sort took :460254 ratio :3.564323771761353
Arrays.sort took :253348 Collections.sort took :474602 ratio :1.8733204919715174

share|improve this answer

answered 13 mins ago

Stefan Steinegger

53.3k13106177

add a comment | 

up vote
0
down vote

up vote
0
down vote

It's only because of unboxing the Integer.

Change the int to Integer, it produces on my machine:

Arrays.sort took :1644305 Collections.sort took :791381 ratio :0.4812860144559555
Arrays.sort took :463652 Collections.sort took :476490 ratio :1.0276888701008515
Arrays.sort took :445529 Collections.sort took :476490 ratio :1.0694926705107861
Arrays.sort took :505184 Collections.sort took :445152 ratio :0.8811680496611136
Arrays.sort took :444775 Collections.sort took :501031 ratio :1.1264819290652577
Arrays.sort took :505185 Collections.sort took :827250 ratio :1.6375189287092846
Arrays.sort took :483286 Collections.sort took :490837 ratio :1.0156242887234475
Arrays.sort took :480265 Collections.sort took :444019 ratio :0.9245291661894995
Arrays.sort took :445152 Collections.sort took :494613 ratio :1.1111103623032133
Arrays.sort took :486306 Collections.sort took :430427 ratio :0.8850949813491916
Arrays.sort took :447417 Collections.sort took :467806 ratio :1.0455704633485092
Arrays.sort took :675468 Collections.sort took :499899 ratio :0.7400779903711204
Arrays.sort took :475357 Collections.sort took :431560 ratio :0.9078650361728132
Arrays.sort took :434203 Collections.sort took :431937 ratio :0.9947812428748765
Arrays.sort took :485174 Collections.sort took :445907 ratio :0.9190661494639036
Arrays.sort took :559177 Collections.sort took :559932 ratio :1.0013501985954358
Arrays.sort took :434203 Collections.sort took :518399 ratio :1.193909300488481
Arrays.sort took :477623 Collections.sort took :445907 ratio :0.9335961626638584
Arrays.sort took :483664 Collections.sort took :444774 ratio :0.9195929405537728

While int on my box produces:

Arrays.sort took :8636850 Collections.sort took :1895765 ratio :0.219497270416876
Arrays.sort took :257123 Collections.sort took :1219542 ratio :4.743029600619159
Arrays.sort took :135924 Collections.sort took :564463 ratio :4.152783908654836
Arrays.sort took :131771 Collections.sort took :558044 ratio :4.234953062509961
Arrays.sort took :124975 Collections.sort took :484418 ratio :3.876119223844769
Arrays.sort took :124220 Collections.sort took :445907 ratio :3.5896554500080504
Arrays.sort took :126107 Collections.sort took :485929 ratio :3.853307112214231
Arrays.sort took :125353 Collections.sort took :525196 ratio :4.189736185013522
Arrays.sort took :168017 Collections.sort took :448173 ratio :2.667426510412637
Arrays.sort took :124975 Collections.sort took :446285 ratio :3.570994198839768
Arrays.sort took :159334 Collections.sort took :447039 ratio :2.8056723612035097
Arrays.sort took :131394 Collections.sort took :448172 ratio :3.4109015632372865
Arrays.sort took :125352 Collections.sort took :446662 ratio :3.5632618546173975
Arrays.sort took :176324 Collections.sort took :522175 ratio :2.961451645833806
Arrays.sort took :125730 Collections.sort took :475735 ratio :3.7837827089795595
Arrays.sort took :124597 Collections.sort took :446285 ratio :3.5818278128686885
Arrays.sort took :125353 Collections.sort took :446662 ratio :3.5632334287970773
Arrays.sort took :147251 Collections.sort took :464408 ratio :3.1538529449715114
Arrays.sort took :168395 Collections.sort took :447417 ratio :2.6569494343656284
Arrays.sort took :243153 Collections.sort took :642242 ratio :2.6413081475449616
Arrays.sort took :129128 Collections.sort took :460254 ratio :3.564323771761353
Arrays.sort took :253348 Collections.sort took :474602 ratio :1.8733204919715174

share|improve this answer

answered 13 mins ago

Stefan Steinegger

53.3k13106177

It's only because of unboxing the Integer.

Change the int to Integer, it produces on my machine:

Arrays.sort took :1644305 Collections.sort took :791381 ratio :0.4812860144559555
Arrays.sort took :463652 Collections.sort took :476490 ratio :1.0276888701008515
Arrays.sort took :445529 Collections.sort took :476490 ratio :1.0694926705107861
Arrays.sort took :505184 Collections.sort took :445152 ratio :0.8811680496611136
Arrays.sort took :444775 Collections.sort took :501031 ratio :1.1264819290652577
Arrays.sort took :505185 Collections.sort took :827250 ratio :1.6375189287092846
Arrays.sort took :483286 Collections.sort took :490837 ratio :1.0156242887234475
Arrays.sort took :480265 Collections.sort took :444019 ratio :0.9245291661894995
Arrays.sort took :445152 Collections.sort took :494613 ratio :1.1111103623032133
Arrays.sort took :486306 Collections.sort took :430427 ratio :0.8850949813491916
Arrays.sort took :447417 Collections.sort took :467806 ratio :1.0455704633485092
Arrays.sort took :675468 Collections.sort took :499899 ratio :0.7400779903711204
Arrays.sort took :475357 Collections.sort took :431560 ratio :0.9078650361728132
Arrays.sort took :434203 Collections.sort took :431937 ratio :0.9947812428748765
Arrays.sort took :485174 Collections.sort took :445907 ratio :0.9190661494639036
Arrays.sort took :559177 Collections.sort took :559932 ratio :1.0013501985954358
Arrays.sort took :434203 Collections.sort took :518399 ratio :1.193909300488481
Arrays.sort took :477623 Collections.sort took :445907 ratio :0.9335961626638584
Arrays.sort took :483664 Collections.sort took :444774 ratio :0.9195929405537728

While int on my box produces:

Arrays.sort took :8636850 Collections.sort took :1895765 ratio :0.219497270416876
Arrays.sort took :257123 Collections.sort took :1219542 ratio :4.743029600619159
Arrays.sort took :135924 Collections.sort took :564463 ratio :4.152783908654836
Arrays.sort took :131771 Collections.sort took :558044 ratio :4.234953062509961
Arrays.sort took :124975 Collections.sort took :484418 ratio :3.876119223844769
Arrays.sort took :124220 Collections.sort took :445907 ratio :3.5896554500080504
Arrays.sort took :126107 Collections.sort took :485929 ratio :3.853307112214231
Arrays.sort took :125353 Collections.sort took :525196 ratio :4.189736185013522
Arrays.sort took :168017 Collections.sort took :448173 ratio :2.667426510412637
Arrays.sort took :124975 Collections.sort took :446285 ratio :3.570994198839768
Arrays.sort took :159334 Collections.sort took :447039 ratio :2.8056723612035097
Arrays.sort took :131394 Collections.sort took :448172 ratio :3.4109015632372865
Arrays.sort took :125352 Collections.sort took :446662 ratio :3.5632618546173975
Arrays.sort took :176324 Collections.sort took :522175 ratio :2.961451645833806
Arrays.sort took :125730 Collections.sort took :475735 ratio :3.7837827089795595
Arrays.sort took :124597 Collections.sort took :446285 ratio :3.5818278128686885
Arrays.sort took :125353 Collections.sort took :446662 ratio :3.5632334287970773
Arrays.sort took :147251 Collections.sort took :464408 ratio :3.1538529449715114
Arrays.sort took :168395 Collections.sort took :447417 ratio :2.6569494343656284
Arrays.sort took :243153 Collections.sort took :642242 ratio :2.6413081475449616
Arrays.sort took :129128 Collections.sort took :460254 ratio :3.564323771761353
Arrays.sort took :253348 Collections.sort took :474602 ratio :1.8733204919715174

share|improve this answer

answered 13 mins ago

Stefan Steinegger

53.3k13106177

share|improve this answer

share|improve this answer

answered 13 mins ago

Stefan Steinegger

53.3k13106177

answered 13 mins ago

Stefan Steinegger

53.3k13106177

answered 13 mins ago

Stefan Steinegger

53.3k13106177

53.3k13106177

add a comment | 

add a comment | 

up vote
0
down vote

if you see Collections.sort() docs it reads

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array

which means it is doing array sort and additional iteration, this implies Collections.sort() is slower than arrays.sort

1. dumps the specified list into an array


2. sorts the array ~ arrays.sort


3. iterates over the list resetting each element from the corresponding position in the array

share|improve this answer

edited 5 mins ago

answered 12 mins ago

The Scientific Method

1,231412

add a comment | 

up vote
0
down vote

if you see Collections.sort() docs it reads

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array

which means it is doing array sort and additional iteration, this implies Collections.sort() is slower than arrays.sort

1. dumps the specified list into an array


2. sorts the array ~ arrays.sort


3. iterates over the list resetting each element from the corresponding position in the array

share|improve this answer

edited 5 mins ago

answered 12 mins ago

The Scientific Method

1,231412

add a comment | 

up vote
0
down vote

up vote
0
down vote

if you see Collections.sort() docs it reads

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array

which means it is doing array sort and additional iteration, this implies Collections.sort() is slower than arrays.sort

1. dumps the specified list into an array


2. sorts the array ~ arrays.sort


3. iterates over the list resetting each element from the corresponding position in the array

share|improve this answer

edited 5 mins ago

answered 12 mins ago

The Scientific Method

1,231412

if you see Collections.sort() docs it reads

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array

which means it is doing array sort and additional iteration, this implies Collections.sort() is slower than arrays.sort

1. dumps the specified list into an array


2. sorts the array ~ arrays.sort


3. iterates over the list resetting each element from the corresponding position in the array

share|improve this answer

edited 5 mins ago

answered 12 mins ago

The Scientific Method

1,231412

share|improve this answer

share|improve this answer

edited 5 mins ago

edited 5 mins ago

edited 5 mins ago

answered 12 mins ago

The Scientific Method

1,231412

answered 12 mins ago

The Scientific Method

1,231412

answered 12 mins ago

The Scientific Method

1,231412

1,231412

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52714131%2fwhy-is-collections-sort-much-slower-than-arrays-sort%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email