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²) 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²) 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[])).