What is the most performant algorithm for sorting array elements?

I am solving UVa site problems, I have a problem that I must sort the integers as fast as possible.

I have tried the bubble sort, but it is inefficient. I have tried the quick sort, which uses开发者_如何学JAVA recursion, but it results a StackOverflowException, since the input is very large (almost 20 millions).

The problem's time limit is only 5 seconds. Does anyone have any ideas on how to implement this more efficiently?

You don't necessarily need to write quicksort recursively.

You can take the recursive algorithm, and rewrite it to use a stack instead, avoiding recursion.

Example implementations of this:

• Friday Algorithms: Iterative Quicksort
• Wikibooks: Algorithm Implementation/Sorting/Quicksort
• CodeProject: Iterative Quick Sort

I'll second the suggestion you consider non-comparison sorts. You say you're sorting integers... what range of integers, specifically, are the values allowed to fall inside? Counting/bucket sort would be silly fast.

I solved the problem using C and the qsort() function, give that a try.

Since you're only sorting integers, radix sort might be a good idea. The nice thing about this algorithm is that its always taking the same amount of time which is dependent on the number of elements to sort and not how "unsorted" they are.

See also Donald Knuth's The Art of Computer Programming volume 3, Sorting and Searching. The algorithm is described in section 5.2.5. Sorting by Distribution, starting at page 168. The algorithm's pseudo-code is Algorithm R on page 172 (page numbers from second edition).

Not only is the algorithm quite efficient, I also think it's easy to understand and implement (well, at least for a sorting algorithm).

Quicksort can be written in-place. Since it does not need (well, not much) additional memory, I don't think it will cause the error if you use this version. If still you have this kind of error, you could consider randomize the input.

Also, you could consider non-comparison sort such as counting sort. These kind of sorting algorithms have their own limitations, but typically needs less time, e.g., O(n).

Use Timsort: http://en.wikipedia.org/wiki/Timsort

Which would not possibly solve your StackOverflow. You can implement them iteratively using a stack.