**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*(*n*^{2}) 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*(*n*^{2}) 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[])).

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?

In C++

`std::sort()`

has worst case performance, so it's not possible to find an input that would reduce it toO(n^{2}) running time like in Java's case. In GNU C++ in particular, the`std::sort()`

function is implemented as Introsort.Thanks for your answer, but there one thing that startles me — the Quicksort idea is always

O(n^{2}) worst case unless we use random pivot, isn't it?BTW, what is implemented as std::sort in MS Visual C++?

Actually, Quicksort has

O(n^{2}) 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 aO(n^{2}) 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.

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 sort

so the std :: sort is an Introspective Sort Algorithm by using three sort algorithms。

By the way as far as I know in Java 7 TimSort is used instead of MergeSort. But it's

`O(nlogn)`

and stable tooi thought Python's sort function used TimSort, not sure if Java too used it.

Here is a blog which might be helpful :

Problems with Java for Competitive Programming

Thank you for the information.

IT SAVED MY DAY

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 - ПриятеЛи

My Submissions:-

(TLE even after using fast IO class):- 84946284

Accepted(even without using Fast IO Reader class) :- 84959537

Use PriorityQueueinstead of Arrays.sort(). Both have Same Time Complexity (nlogn)Is there a 2 * 10^5 size input that forces O(n^2) time complexity for Arrays.sort()? If yes, we can keep it for future hacks in contest.

use c++