Quicksort is an inplace sort (unless the implementation is bad). It can
be implemented with recursion or iteration with an array as stack. (The
latter is e.g. described in Numerical Receipes.) Did you perhaps use
mergesort?
If you wrote quicksort as recursion, beware that some Fortran compilers
might use copy-in copy-out semantics. The solution is to use C or
iterative quicksort with an array as stack.
Quicksort is also O(n**2) worst case, heapsort or mergesort is always
O(n log n). There is a version of mergesort with controlled memory use
called timsort, which is used by Python and Java standard libraries.
Sturla Molden
On 08.02.2012 16:14, Aleksandar Donev wrote:
> Hello,
> Does someone have a (public) code (preferably Fortran, but C is also OK
> given C Interoperability) that can sort a large (1 billion elements)
> array (say, reals) in place? The array is not huge, i.e., it fits in
> memory, but still large. Quicksort, which I usually use, is recursive
> and its memory usage quickly went out of control. Speed is not of utmost
> importance though obviously O(N^2) won't do.
> Thanks,
> Aleks
>
|