Abstract
I will describe how to avoid a TLE (timelimit exceeded) in competitive programming when sorting an array in Java.

Introduction
Consider the following task. You are given an array of integers and have to sort it. A convenient way to do this is to use the built-in function Arrays.sort() in Java.

import java.util.*;

public class Main {

	public static void main(String[] args) {

		// sort array with primitive datatype int.
		// quicksort is applied.
		int[] arr_A = {5,3,1,4,6,2};
		System.out.print("Original: ");
		printArray(arr_A);

		Arrays.sort(arr_A);
		System.out.print("Sorted:   ");
		printArray(arr_A);

	}

	static void printArray(int[] arr){
		for(int i=0; i<arr.length; ++i){
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

}

The output is:

Original: 5 3 1 4 6 2
Sorted:   1 2 3 4 5 6

However, Arrays.sort() uses quicksort if you pass an array of primitive datatype to it. Quicksort has on average a runtime of , but keep in mind that it has a worst-case runtime of . The worst-case runtime occurs if you try to sort an array that is almost sorted. This yields a TLE (timelimit exceeded) verdict by the online judge. We can avoid this with two methods.

Method 1: Use objects (wrapper class)
It is useful to know that Java uses mergesort to sort arrays that contain objects. Thus, the idea is to replace the primitive datatype int with its wrapper class Integer:

int[] array -> Integer[] array

Integer[] array is an array whose elements are objects and will be sorted with mergesort when using Arrays.sort(). The code below illustrates this:

import java.util.*;

public class Main {

	public static void main(String[] args) {

		// Method 1:
		// Enforce mergesort by using
		// datatype Integer (wrapper class of int).
		// arr_B_Objects contains objects.
		int[] arr_B = {-5,3,-1,4,-6,2};
		System.out.print("Original: ");
		printArray(arr_B);

		Integer[] arr_B_Objects = new Integer[arr_B.length];
		for(int i=0; i<arr_B.length; ++i){
			arr_B_Objects[i] = new Integer(arr_B[i]);
			// or simply arr_B_Objects[i] = arr_B[i];
		}

		Arrays.sort(arr_B_Objects);     // mergesort
		System.out.print("Sorted:   ");
		printArray(arr_B_Objects);

	}

	static void printArray(int[] arr){
		for(int i=0; i<arr.length; ++i){
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	static void printArray(Integer[] arr){
		for(int i=0; i<arr.length; ++i){
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

}

The output is:

Original: -5 3 -1 4 -6 2
Sorted:   -6 -5 -1 2 3 4

Method 2: Shuffle the array before quicksort
We have mentioned that quicksort has a worst-case runtime of for almost sorted arrays. Thus, we will first shuffle the array and then apply quicksort.

import java.util.*;

public class Main {

	public static void main(String[] args) {

		// Method 2: Shuffle the primitive datatype
		// array before using quicksort
		int[] arr_C = {1,2,3,4,6,5};
		System.out.print("Original: ");
		printArray(arr_C);

		shuffleArray(arr_C);
		System.out.print("Shuffled: ");
		printArray(arr_C);

		Arrays.sort(arr_C);
		System.out.print("Sorted:   ");
		printArray(arr_C);

	}

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

	static void printArray(int[] arr){
		for(int i=0; i<arr.length; ++i){
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

}

The output is:

Original: 1 2 3 4 6 5
Shuffled: 2 1 5 3 4 6
Sorted:   1 2 3 4 5 6

Note:
I have encountered this issue when trying to solve problem 285C – Building Permutation on Codeforces.

References
[1] More On Shuffling An Array Correctly – blog post by Ryan Rampersad.
[2] Why java Arrays use two different sort algorithms for different types? (discussion on stackoverflow.com)
[3] Java doc on quicksort and mergesort