What is the best sorting algorithm to sort an array of small integers?

As per question title, if the array is of an odd length and the array elements are numbered 1 - 10.

Example,

3 6 8 1 3 7 7 9 4 1

I was thinking of using heapsort? Since it is an array, merge sort and insertion sort requ开发者_如何学Goires shifting, and would not be so efficient.

the array elements are number from 1 - 10.

With this restriction, counting sort will be far more efficient than any general purpose sorting algorithm - it's O(n)

This is my counting sort example

static int[] countingSort(int[] numbers) {
    int max = numbers[0];
    for (int i = 1; i < numbers.length; i++) {
        if (numbers[i] > max)
            max = numbers[i];
    }

    int[] sortedNumbers = new int[max+1];

    for (int i = 0; i < numbers.length; i++) {
        sortedNumbers[numbers[i]]++;
    }

    int insertPosition = 0;

    for (int i = 0; i <= max; i++) {
            for (int j = 0; j < sortedNumbers[i]; j++) {
                    numbers[insertPosition] = i;
                    insertPosition++;
            }
    }
    return numbers;
}

If there are only 10 elements it isn't worth your while to even worry about it. If there are a million it might start to become significant.

Edit: A counting sort is probably optimal given the constraint that the elements only range from 1-10. A counting sort applied to this problem will run in O(n) time. A merge sort (as I recommended below) will run in no better than O(nlogn) time. Parallelizing a counting sort could be interesting. Simply assign a subarray with n/p elements to each processor. Each processor would have its own count array of size 9. This step should take O(n/p) time. Then consolidate all the count arrays into a single array, which should take O(p) time. I haven't fully thought through the last step in the counting sort where the elements are placed in order, but it seems as long as the elements of the count array are atomic, you could assign n/p sections of the original array to individual processors and achieve some parallelization. There would be contention at individual elements of the count array, however, potentially substantially reducing concurrency. You might be able to assign subsections of the count array to p processors and you are back to O(n/p) runtime, if the elements are distributed fairly evenly, but you would be limited to 10 processors. If the elements are not distributed evenly, one or more processors could be doing a larger proportion of the work. This is great question; can you do a counting sort in O(n/p) time?

Quicksort is a great in-place sort algorithm that runs fast and conserves memory. However, given the elements only range from 1-10, if you are sorting large numbers of elements, you will end up with large runs of the same number, either initially, or at interim times during the sort. In-order arrays or sub-arrays can really bog down a Quicksort's performance.

If you don't care about memory, a simple Mergesort would suffice. Mergesort is up there with the fastest standard sort algorithms.

The default Collections.sort() implementation in Java 7 is a Mergesort algorithm adapted from 'TimSort.' The default Arrays.sort() implementation in Java 7 is a dual pivot Quicksort.

If you would like to go parallel, a Parallel Quicksort can achieve good results on large arrays with small numbers of processors, but with the same limitations as the sequential Quicksort. PSRS can help scale to larger numbers of processors.

You should consider looking at this for complexity chart Complexity Comparison Chart.

The comparison of sorting algorithm is based on their Best, Average, Worst case scenario for time and space complexity.Based on this chart you can see Counting Sort approach is best on both space and time complexity. Other comparable method is Radix Sort.

Worst [Time,Space] complexity of "Counting Sort" :- [O(n+k),O(k)].

Worst [Time,Space] complexity of "Radix Sort" :- [O(nk),O(n+k)].

this is an example of simple sort (Insertion sort)

private static void insertionSort(int[] a) {

    // [230, 23, 45, 34, 98]
    for (int j = 2; j < a.length; j++) {

        int key = a[j];
        int i = j - 1;

        while (i > 0 && a[i] > key) {
            a[i + 1] = a[i];
            i--;
        }
        a[i + 1] = key;
    }

    System.out.println("sorted array: " + Arrays.toString(a));
}

Counting sort will be best in this scenario.

Assuming the data are integers, in a range of 0-k. Create an array of size K to keep track of how many items appear (3 items with value 0, 4 items with value 1, etc). Given this count, you can tell the position of an item — all the 1’s must come after the 0’s, of which there are 3. Therefore, the 1’s start at item #4. Thus, we can scan the items and insert them into their proper position.

Creating the count array is O(N) Inserting items into their proper position is O(N) I oversimplified here — there is a summation of the counts, and a greatest-to-least ordering which keeps the sort stable.

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot and then repeats the process. There are many different versions of quickSort that pick pivot in different ways