How to sort an array in the kernel?

Question

I want to sort a large array of strings (especially File.list() , which I cannot export or reduce further) without using [large] extra memory.

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

Is there an in-place sorting algorithm instead that is memory efficient?

Answer 1

quicksort in place and very fast. See here .

Answer 2

String immutable in Java. That way, when the String array in your question is duplicated, they do not require as much space as you expect. In fact, overhead can be minimal.

In other words, Java Arrays#sort() might just be great for your solution. You can check the performance yourself.

For your Ankit answer and dlev question title, the answer is just perfect.

Answer 3

You can write a heap sorting algorithm to sort in place.