Sorting an array which the maximum value is similar to its size <p>I'm trying to figure out the best way to sort an array which the maximun value is similar to its size. The array does not contain repeated elements.</p> <pre><code>import java.util.Arrays; import java.util.Random; public class SortExamples { public static void main(String[] args) { SortExamples sortExample = new SortExamples(); int[] sizes = { 10000, 100000, 500000, 750000, 1000000, 1500000, 2000000, 5000000, 7500000, 10000000, 15000000 }; SortingMethod arraySort = new ArraySort(); SortingMethod quickSort = new QuickSort(); for (int i = 0; i &lt; sizes.length; i++) { System.out.println("Sorting array of length: " + sizes[i]); int[] array1 = sortExample.getArraySample(sizes[i]); int[] array2 = Arrays.copyOf(array1, array1.length); assert Arrays.equals(array1, array2); sortExample.sort(array1, arraySort); sortExample.sort(array2, quickSort); assert Arrays.equals(array1, array2); System.out.println(); } } public void sort(int[] array, SortingMethod sortingMethod) { assert !checkOrdered(array); long startTime = System.currentTimeMillis(); sortingMethod.sort(array); long endTime = System.currentTimeMillis(); System.out.println("Total time with " + sortingMethod.getClass().getSimpleName() + ": " + (endTime - startTime) + " millis."); assert checkOrdered(array); } public int[] getArraySample(int size) { int[] array = new int[size]; for (int i = 0; i &lt; size; i++) array[i] = i; shuffle(array); return array; } /** * Same as java.util.Collections.shuffle(List&lt;?&gt;, Random) * * @param array */ public void shuffle(int[] array) { Random random = new Random(); int count = array.length; for (int i = count; i &gt; 1; i--) swap(array, i - 1, random.nextInt(i)); } public boolean checkOrdered(int[] array) { for (int i = 1; i &lt; array.length; i++) if (array[i] &lt; array[i - 1]) return false; return true; } public static class ArraySort implements SortingMethod { public void sort(int[] array) { if (array.length &lt; 2) return; Integer[] auxiliarArray = new Integer[getMax(array) + 1]; for (int i = 0; i &lt; array.length; i++) { int current = array[i]; auxiliarArray[current] = current; } int k = 0; for (int j = 0; j &lt; auxiliarArray.length; j++) { Integer current = auxiliarArray[j]; if (current != null) { array[k] = current; k++; } } } public int getMax(int[] array) { int max = array[0]; for (int i = 0; i &lt; array.length; i++) if (max &lt; array[i]) max = array[i]; return max; } } public static class QuickSort implements SortingMethod { public void sort(int[] array) { sortInternal(array, 0, array.length - 1); } public void sortInternal(int[] array, int start, int end) { int i = start; int j = end; int pivot = array[(start + end) / 2]; while (i &lt;= j) { while (array[i] &lt; pivot) i++; while (array[j] &gt; pivot) j--; if (i &lt;= j) { swap(array, i, j); i++; j--; } } int startLeft = start; int endLeft = i - 1; if (startLeft &lt; endLeft) sortInternal(array, startLeft, endLeft); int startRigth = i; int endRigth = end; if (startRigth &lt; endRigth) sortInternal(array, startRigth, endRigth); } } public interface SortingMethod { public void sort(int[] array); } public static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } </code></pre> <p>The output I got was:</p> <pre><code>Sorting array of length: 10000 Total time with ArraySort: 2 millis. Total time with QuickSort: 2 millis. Sorting array of length: 100000 Total time with ArraySort: 14 millis. Total time with QuickSort: 16 millis. Sorting array of length: 500000 Total time with ArraySort: 22 millis. Total time with QuickSort: 59 millis. Sorting array of length: 750000 Total time with ArraySort: 25 millis. Total time with QuickSort: 91 millis. Sorting array of length: 1000000 Total time with ArraySort: 33 millis. Total time with QuickSort: 122 millis. Sorting array of length: 1500000 Total time with ArraySort: 66 millis. Total time with QuickSort: 191 millis. Sorting array of length: 2000000 Total time with ArraySort: 100 millis. Total time with QuickSort: 278 millis. Sorting array of length: 5000000 Total time with ArraySort: 391 millis. Total time with QuickSort: 662 millis. Sorting array of length: 7500000 Total time with ArraySort: 2805 millis. Total time with QuickSort: 1033 millis. Sorting array of length: 10000000 Total time with ArraySort: 3629 millis. Total time with QuickSort: 1409 millis. Sorting array of length: 15000000 Total time with ArraySort: 3825 millis. Total time with QuickSort: 2185 millis. </code></pre> <p>Is this an existing method? Could it be useful for something?</p>