Can a MongoDB key have two arrays?

How would you design an algorithm that merges n sorted arrays into one, if we can only merge two arrays at a time and we want to minimize the total number of  times we move an element?

• Assume you are given n sorted arrays of different sizes. You are allowed to merge any two arrays into a single new sorted array and proceed in this manner until only one array is left. How would you design an algorithm that achieves this task and uses minimal total number of moves of elements of the arrays. And what is an informal justification you would give why your algorithm is optimal?

• Answer:

  A greedy strategy works: always merge the two shortest arrays into a new one. Below I assume that merging two arrays with aa and b elements into one requires exactly a+b moved elements. For this model, I can actually formally prove that my answer is optimal. Visualize the order in which you merge the arrays as a binary tree. The leaves are the original arrays, each inner vertex represents a merge, and the root corresponds to the result. Now, look at any original array. How many times will we move each of its elements during the entire process? The answer is clearly equal to the depth of the leaf that corresponds to this array. Hence, we have n different arrays and we are trying to construct a binary tree with n leaves such that sum (array length) * (assigned leaf depth) is minimized. This is the well-known optimal prefix code problem which has a provably optimal solution: the http://en.wikipedia.org/wiki/Huffman_coding (For a sketch of the proof: If you knew the shape of the tree, you would always put the longest arrays into the most shallow leaves, and shortest arrays into the deepest ones. In particular, the two shortest arrays would end up at the deepest level. Without loss of generality, they can be in sons of the same vertex, which gives the greedy algorithm proposed above.)