How do I perform a memory-efficient array sort in java?

Question

I'm wanting to sort a large array of Strings (notably File.list(), which I cannot externalise or reduce further) without using [much] extra memory.

Arrays.sort() says it does a merge sort, and wikipedia says that some implementations allocate the size of the original array for storing the sorted output. (This seems to be supported by the System.arraycopy reference in the method).

Is there an in-place sorting algorithm I can use instead which is memory efficient?

Answer 1

String is immutable in Java. Thus when the array of Strings in your question are duplicated, they do not require as much space as you expect. Actually, the overhead can be quite minimal.

In other words, Java's Arrays#sort() can be just fine for your solution. You may test the performance yourself.

For your title of the question, Ankit's answer and dlev's answer are just fine.

Answer 2

You can write an Heap Sort algorithm for in-place sorting.

Answer 3

quicksort is in-place and very fast. See here.