### Flatfoot's blog

By Flatfoot, 8 years ago,

Abstract

Below I will describe how to avoid TLE (timelimit exceeded) when sorting an array in Java. I will describe two methods.

Introduction

When trying to sort an array in Java it is convenient to use Arrays.sort():

long[] arr = {5,3,4,2,1};
Arrays.sort(arr);
// after sorting print arr


However, this method uses quicksort if the array contains elements of primitive datatype such as long or int. Quicksort has on average a runtime of , but keep in mind that the worst-case runtime is O(n2) for arrays that are almost sorted. As a consequence you can get a TLE (timelmit exceeded) by the online judge. Below are two methods that avoid this issue.

Method 1: Use objects (wrapper class)

We will use the wrapper class Long of the primitive datatype long. Given an array long[] arr we will introdue an array Long[] arr_obj. While long[] arr is sorted with quicksort Long[] arr_obj is sorted with mergesort which has a worst-case runtime of . In Java an array with objects is sorted with mergesort when using Arrays.sort().

long[] arr = {5,3,4,2,1};
int n = arr.length;
Long[] arr_obj = new Long[n];
for(int i=0; i<n; ++i){
arr_obj[i] = new Long(arr[i]);
}
Arrays.sort(arr_obj);
// after sorting print arr_obj


Method 2: shuffling the array before quicksort

We can still use quicksort but in order to avoid the worst-case runtime of O(n2) for an almost sorted array we will first shuffle it and then apply quicksort.

long[] arr = {1,2,3,5,4};
shuffleArray(arr);
Arrays.sort(arr);
// after sorting print arr


The function shuffleArray() is given by

void shuffleArray(long[] arr){
int n = arr.length;
Random rnd = new Random();
for(int i=0; i<n; ++i){
long tmp = arr[i];
int randomPos = i + rnd.nextInt(n-i);
arr[i] = arr[randomPos];
arr[randomPos] = tmp;
}
}


References

[1] [More On Shuffling An Array Correctly](http://blog.ryanrampersad.com/2012/03/more-on-shuffling-an-array-correctly/) – blog post by Ryan Rampersad.

[2] [Why java Arrays use two different sort algorithms for different types?](http://stackoverflow.com/questions/3707190/why-java-arrays-use-two-different-sort-algorithms-for-different-types) (discussion on stackoverflow.com)

[3] Java doc on [quicksort](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(long[])) and [mergesort](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])).

• +31

 » 8 years ago, # |   0 Can anyone by the way explain why C++ std::sort in work fast?Does it use randomized pivot during sorting?Can I generate a test where std::sort gets TL?
•  » » 8 years ago, # ^ |   +1 In C++ std::sort() has worst case performance, so it's not possible to find an input that would reduce it to O(n2) running time like in Java's case. In GNU C++ in particular, the std::sort() function is implemented as Introsort.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 Thanks for your answer, but there one thing that startles me — the Quicksort idea is always O(n2) worst case unless we use random pivot, isn't it?BTW, what is implemented as std::sort in MS Visual C++?
•  » » » » 8 years ago, # ^ |   0 Actually, Quicksort has O(n2) worst case performance even if you choose the pivot randomly. It's just that the probability of this happening is almost zero, and no "bad" test can be prepared in advance. But if you are extremely unlucky, you could hit a O(n2) run time even with a random pivot or shuffle.As for MS C++, I don't know, but it still must have worst case performance.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I remember the std :: sort use three algorithms, First it takes the quicksort while the len of the array Higher than a threshold, Because the quicksort uses recursion, when the len lower than a threshold it takes insertation sort. Because the part of the array is almost in order, so it takes about O(N) time. When the recursive level is too deep. (sorry for my poor English) It takes another Nlogn algorithm — heap sort, in order to avoid the N^2 quick sortso the std :: sort is an Introspective Sort Algorithm by using three sort algorithms。
 » 8 years ago, # |   +2 By the way as far as I know in Java 7 TimSort is used instead of MergeSort. But it's O(nlogn) and stable too
 » 3 years ago, # |   0 Here is a blog which might be helpful :Problems with Java for Competitive Programming
 » 2 years ago, # |   0 Thank you for the information.IT SAVED MY DAY
 » 8 months ago, # |   +5 If anyone is looking for a problem causing issues with Arrays.sort() here it is. I found recently a problem and faced the same issue. Problem Link:- 1369C - RationalLeeMy Submissions:- (TLE even after using fast IO class):- 84946284 Accepted(even without using Fast IO Reader class) :- 84959537
 » 6 months ago, # |   0 Use PriorityQueue instead of Arrays.sort(). Both have Same Time Complexity (nlogn)