0

I found Java's Arrays.sort() method is much slower than my simple sorting method (based on counting sort).

I wrote a program to compare running time my simple sorting technique with Java's Arrays.sort() method. I noticed my implementation runs much faster (it needs 1/3 time compared with system method).

Below is my implementation.

I keep track of all the elements in a secondary array and I copied back all the elements to the main array before return. 

static void mySort(int[] num2, int n)
{
    double startTime, endTime;

    startTime = System.currentTimeMillis(); 
    int[] sortedData = new int[n];

    for (int i = 0; i < n; i++)
       sortedData[num2[i]]++;

    int index = 0;
    for (int i = 0; i < n; i++)
       if (sortedData[i] > 0)
       {
          for (int j = 0; j < sortedData[i]; j++)
          {
             num2[index++] = i;
          }
       }

     endTime = System.currentTimeMillis(); 

     System.out.println("Time taken for my sort: " 
           + (endTime - startTime) +  " ms");
 }


 static void systemSort(int[] num)
 {
     double startTime, endTime;

     startTime = System.currentTimeMillis(); 
     Arrays.sort(num);
     endTime = System.currentTimeMillis(); 

     System.out.println("Time taken for System sort: " + 
                     (endTime - startTime) + " ms");
 }


 public static void main(String[] args)
 {

  int size = 50000000;
  int[] origArray = new int[size];
  int[] origArray2 = new int[size];

  Random rn = new Random();

  System.out.println("Taking " + size + " inputs randomly...");
  for (int i = 0; i < size; i++)
  {
     origArray[i] = rn.nextInt(size);
     origArray2[i] = origArray[i];
  }
  System.out.println("Done!");

  System.out.println("\n\nFrom System sort:  ");
  systemSort(origArray);

  System.out.println("\n\nFrom my sort:  ");

  mySort(origArray2, size);
}

Here is the output:

Taking 5000000 inputs randomly...

Time taken for System sort: 652.0 ms

Time taken for my sort: 160.0 ms

Taking 50000000 inputs randomly...

Time taken for System sort: 5737.0 ms

Time taken for my sort: 2176.0 ms

If we can buy a good amount of execution time with the cost of memory (considering memory is less expensive now a days) then why not we taking advantages of it?

Any thoughts? Thank you.

User_67128
  • 1,230
  • 8
  • 21
  • 3
    It looks like you have a requirement that no value of the array can be larger than the array length-1. The buit-in sort has no such requirement. You have a very specialized case. The built-in sort needs to be able to handle any values. – 001 Jun 04 '19 at 17:03
  • Yeah, you are absolutely right. This technique is not applicable for all cases. I got that. Thank you. – User_67128 Jun 04 '19 at 17:14
  • 1
    Nor does it handle negative numbers in the original array, as it relies on the convenience of assigning a number to that index of the sorted array equal to its value and Java allows no index below zero. – Trunk Jun 04 '19 at 18:45

1 Answers1

2

because you will need array of size(int), or 4 giga, here you do just <50 M. And for long its realy imposible. Try something more clever like at least count-sort upper bytes (short), then for each range of equal upper bytes countsort lower bytes...

user8426627
  • 903
  • 1
  • 9
  • 19
  • Oh yes, I can improve this one. Thank you. – User_67128 Jun 04 '19 at 17:12
  • show me your solution i ll compare with mine – user8426627 Jun 04 '19 at 17:14
  • 1
    Besides the flaws of the “benchmark” of the question’s code, this is the correct consideration. For an arbitrary `int[]` array, the value range is too large to make a counting sort in general. Note that it isn’t even possible to create an array with 2³² elements in Java, you’d need at least two, and the amount of memory is 4 byte × 2³² elements, in other words 16 GiB. For `byte[]`, `short[]`, and `char[]`, `Arrays.sort` does counting sort when the array length justifies it. See also [this answer](https://stackoverflow.com/a/32334651/2711488). – Holger Feb 14 '20 at 08:18