Merge sort: Vec<T> vs Vec<Vec<T>>

1

  1. Suppose we are doing merge sort of A & B, of n_A and n_B elements.

  2. If A, B, and output are stored as Vec, then we will need:

( n_A + n_B + (n_A + n_B) * sizeof(T) bytes of storage

  1. On the other hand, if we stored A, B, and outputa s Vec<Vec> ... with the inner Vec having K elements, then at any given time, we will only need:

(n_A + n_B + K * 2) * sizeof(T) + (n_A/k + n_B/k)*sizeof(ptr) bytes of storage right?

Because if we into_iter A and B, we consume Vec's of size K as we march along / allocate new blocks in the output.

  1. If the above is correct, does Rust have any crates built around Vec<Vec> ?
2

I don't know whether there exists any crate that offers such a data structure. Since the memory savings are only a factor of two I wonder how useful this is in practice. If your input vectors are so large that a factor of two will make the difference between fitting in memory and not fitting in memory, a more common solution would be to stream over the input data instead of keeping it in memory in the first place.

1 Like
3

Yeah, that's a good point.:

2 * data > RAM > data

is a very rare situation indeed.