Java | Handling TLE While Using Arrays.sort() Function

In programming it is quite usual for a Java programmer to face time limit exceeded or TLE if they do not use Arrays.sort() function carefully.

Below java code shows the run time taken by the trivial Arrays.sort() function.

Time Taken By The Use of Trivial Arrays.sort() function : 31ms

As we can see, the time taken is quiet high for sorting of 1 million numbers, at first sight, it might seem not so high but during programming contest, each millisecond brings about a difference.

Reason For TLE:
Arrays.sort() function uses Quick Sort in its implementation. The worst-case complexity of Quick Sort is O() where N is the size of the array. The worst-case complexity comes in the case where input array is already sorted and most of the time problem setters like to make such test cases.

How To Handle The Worst Case:

1. Using an Array Of Objects (Wrapper Classes of Primitives) Instead of Values:
   Instead of using an array of values, sorting of object array takes lesser time. It is because Arrays.sort() function uses Merge Sort for sorting object array, which has a worst-case complexity of O() in comparison to quick sort’s O().

   Below java code shows the run time comparison between using Arrays.sort() function on the array of values with that on the array of objects.

   
   

   
   
   

   // Java program to handle worst case // of Arrays.sort method    import java.util.Arrays; import java.util.Calendar;    public class ArraySort {        // function to fill array with values     void fill(int a[], int n)     {         for (int i = 0; i < n; i++)             a[i] = i + 1;     }        // function to fill array with     // objects     void fill2(Integer a[], int n)     {         for (int i = 0; i < n; i++)             a[i] = new Integer(i + 1);     }        // function to compare performance     // of original and optimized method 1     void performanceCheckOfSorting()     {         // creating a class object         ArraySort obj = new ArraySort();            // variables to store start         // and end of operation         long startTime = 0l;         long endTime = 0l;            // Method 1         // Using Arrays.sort()         int array1[] = new int[100000];         int n = array1.length;            // calling function to fill array with         // values         obj.fill(array1, n);            startTime = Calendar.getInstance()                         .getTimeInMillis();         // sorting the obtained array         Arrays.sort(array1);         endTime = Calendar.getInstance()                       .getTimeInMillis();            // printing the total time taken         // by Arrays.sort in worst case         System.out.println("Time Taken By Arrays.sort"                            + " Method On Values : "                            + (endTime - startTime)                            + "ms");            // Method 2         // Taking Array Of Type Object         Integer array2[] = new Integer[n];            // calling function to fill array with         // objects of class Integer         obj.fill2(array2, n);            startTime = Calendar.getInstance()                         .getTimeInMillis();         Arrays.sort(array2);         endTime = Calendar.getInstance()                       .getTimeInMillis();            // printing the total time taken         // by Arrays.sort in case of object array         System.out.println("Time Taken By Arrays.sort"                            + " Method On Objects: "                            + (endTime - startTime)                            + "ms");     }        // Driver function     public static void main(String args[])     {         // creating object of class         ArraySort obj = new ArraySort();            // calling function to compare performance         obj.performanceCheckOfSorting();     } }
   Output:

   Time Taken By Arrays.sort Method On Values : 31ms
   Time Taken By Arrays.sort Method On Objects : 19ms
   

   Here we can see that time taken by Arrays.sort() function to sort the array of the object is less than the arrays of values.

2. Shuffling Before Sorting:
   This method is most frequently used by competitive java programmers. The idea is to shuffle the whole input array
   before sorting, in this way the worst case of quicksort which arises in the case of the already sorted array is handled.
   Another benefit of this method is, it maintains the primitive nature of the array.

   In the following Java program, I have shown a comparison between trivial use of Arrays.sort() function and that after shuffling the whole array. I have also provided the implementation of user-defined shuffle method having the complexity of O() of shuffling where N is the size of the array.

   
   

   
   
   

   // Java program to handle worst-case // of Arrays.sort method    import java.util.Arrays; import java.util.Calendar;    public class ArraySort {        // function to fill array with values     void fill(int a[], int n)     {         for (int i = 0; i < n; i++)             a[i] = i + 1;     }        // Java implementation of shuffle     // function     void shuffle(int a[], int n)     {         for (int i = 0; i < n; i++) {                // getting the random index             int t = (int)Math.random() * a.length;                // and swapping values a random index             // with the current index             int x = a[t];             a[t] = a[i];             a[i] = x;         }     }        // function to compare performance     // of original and optimized method 2     void performanceCheckOfSorting()     {         // creating a class object         ArraySort obj = new ArraySort();            // variables to store start         // and end of operation         long startTime = 0l;         long endTime = 0l;            // Using Arrays.sort()         // without shuffling before sorting         int array1[] = new int[100000];         int n = array1.length;            // calling function to fill array with         // values         obj.fill(array1, n);            startTime = Calendar.getInstance()                         .getTimeInMillis();         // sorting the obtained array         Arrays.sort(array1);         endTime = Calendar.getInstance()                       .getTimeInMillis();            // printing the total time taken         // by Arrays.sort in worst case         System.out.println("Time Taken By Arrays.sort"                            + " Method On Trivial Use: "                            + (endTime - startTime)                            + "ms");            // Shuffling before Sorting         // calling function to fill array with         // values         obj.fill(array1, n);            // calling function to shuffle         // obtained array         obj.shuffle(array1, n);            startTime = Calendar.getInstance()                         .getTimeInMillis();         Arrays.sort(array1);         endTime = Calendar.getInstance()                       .getTimeInMillis();            // printing the total time taken         // by Arrays.sort() function in case shuffling         // of shuffling before sorting         System.out.println("Time Taken By Arrays.sort"                            + " Method After Shuffling "                            + "Before Sorting : "                            + (endTime - startTime)                            + "ms");     }        // Driver function     public static void main(String args[])     {         // creating object of class         ArraySort obj = new ArraySort();            // calling function to compare performance         obj.performanceCheckOfSorting();     } }
   Output:

   Time Taken By Arrays.sort() Function On Trivial Use : 31ms
   Time Taken By Arrays.sort() Function After Shuffling Before Sorting : 10ms
   

   Here, in this case, we see that using Arrays.sort() function on shuffled array takes lesser time in comparison to that on the unshuffled array. Also, time taken in sorting the array of objects is more than the time taken for sorting arrays after shuffling.