“In-place” iterative LSD n-radix sort

0
votes

Is it possible to implement a "in-place" iterative LSD n-radix sort? To clarify: I've read the wikipedia atricle on in-place MSD radix sort. There it says that:

Counting sort is used to determine the size of each bin and their starting index.

and therefore an auxiliary array is needed to store the indexes but if that is all that it needs I still consider it to be a in-place algorithm (since this array would only be of size n for a n-radix sort). I have also read this answer where once again a recursive MSD radix sort is implemented. That one also has no general implementation for a n-radix sort.

1
algorithmsortingradix-sortin-place
For the general case, two auxiliary arrays are needed, or one array of pairs. Each bin requires a starting index and a dynamic count of elements (the count starts at zero and increase as elements are stored into a bin). As noted in the wiki article, the scanning of the array has to skip over the elements already stored in bins. – rcgldr

1 Answers

0
votes

EDIT: I've finally described my algorithm in the answer here: https://cs.stackexchange.com/questions/93563/fast-stable-almost-in-place-radix-and-merge-sorts

Yes. Virtually split input data into pages of some size (4 KB will serve well). Then reuse these pages as you consumed their data. You will need some extra memory, though - up to n pages for initial buckets, next-page pointers (one pointer per page), 3*n pointers for head_page/current_page/current_write_ptr per bucket

The algo:

  1. Alloc n pages and put them into list of free pages
  2. Process input data, moving entries into their buckets. Once entire page of input data is processed, add this page to the list of free pages. Once entire bucket page is filled, add it to the list of this bucket pages and alloc new one from free list. You will end up with list of pages per each bicket, last page in this list is partially filled
  3. Move data around to fit it back to the original array in the order of buckets

Of course, if you need multiple LSD passes, you can skip step 3 except for last pass and start each sorting pass directly from list built at step 2. It will require n extra pages, though.