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.

Improve this question
$\endgroup$
1
  • 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
    Commented Mar 29, 2016 at 17:33

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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