0
$\begingroup$

Is there an in-place algorithm for sorting variable length records?

For example a vector of arbitrary length strings.

Most provided in-place algorithms assume that you can switch two elements without affecting the rest of the structure. However this does not work if your records differs in size.

Googling leads me to this. However, they finish with:

After writing all sorted output blocks, merge them into the final sorted file using any convenient merging algorithm. When allocating buffers or making other preparations, the merging steps can take advantage of the fact that every variable-length block written by step 7 has the same maximum size (just less than the size of buffer 1 or 2)." I do not feel that doing in-place merging of arbitrary length records is in any way trivial.

$\endgroup$
  • 1
    $\begingroup$ What exactly would the input look like? Usually, you'd have pointers to the records so every in-place sorting algorithm would do. Do you really propose to store the data sequentially? It's pretty clear that you will never be able to maintain such a thing efficiently, and that pretty much precludes in-place sorting. $\endgroup$ – Raphael Mar 29 '16 at 17:33
1
$\begingroup$

If we're just dealing with packed variable-length records, swapping two adjacent elements is not difficult, so bubble sort will work.

There are some techniques for creating space while sorting to use for auxiliary data structures, based on the fact that (partially) sorted data has less entropy than unsorted. See Radix Sorting With No Extra Space by Franceschini, Muthukrishnan, and Patrascu for examples. They don't deal with variable length records specifically, but some of the ideas there might be useful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.