Merging a list of lists into a single list with minimal comparisons

Question

I'm attempting to merge a list of lists into one master sorted list. (It's a list of lists of strings in C#, but the type isn't really relevant here)

There's a similar problem here How to merge a list of lists with same type of items to a single list of items? but my requirements are different.

Every comparison I make is going to be based on user input, so I can't do any sort of all-at-once LINQ thing like the other question. I have to ask the user which item is 'better' for every single comparison.

My initial idea was to effectively copy the 'merge' part of 'mergesort', and repeatedly use binary search for each new term popped off the second list in each merge.

However, I still don't know what would be the most efficient order to merge the lists. Should I merge smallest with smallest, and build up size progressively that way? Or would it be better to have a designated big list that the small lists get merged into once? I'm not sure how to go about proving this either way.

How would I merge these lists of arbitrary size whilst performing the minimum number of user-facing comparisons?

interesting question, but will probably be more relevant on CodeReview or Programmers ? — Noctis
– Noctis, Commented Oct 21, 2014 at 1:33
Please elaborate, to make clear what you want to do. Are the original lists already sorted? What do you mean by "binary search? Are you saying you're going to use an insertion sort, with a binary search to find the insertion point? But why not sort the original lists and then do a proper merge sort? Finally note that if you are using the user as the actual comparator, you need to figure out how you're going to detect and deal with inconsistent user input. It's pretty optimistic to expect a user will satisfy the transitive requirement for all sort comparisons on any significant size of data. — Peter Duniho
– Peter Duniho, Commented Oct 21, 2014 at 2:48

govin · Accepted Answer · 2014-10-21 05:41:46Z

1

Given that none of those lists are sorted, and you don't have any pre-existing knowledge about the data in the lists, you cannot do this better than O(nlogn) comparisons. Here n is size(list 1) + size(list 2) +...size(list final).

You can simply iterate through the list of lists and construct a master list with n elements. Then you can sort the master list using either quick sort or merge sort. The time complexity would be O(nlogn) for sorting. There is an additional memory of O(n) for the master list.

So you would ask the user about nlogn times. You can minimize the number of times you ask the user about comparison by caching the results of the prior comparisons and not asking the user the same comparison again.

edited Oct 21, 2014 at 5:41

answered Oct 21, 2014 at 4:41

govin

6,7635 gold badges46 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Merging a list of lists into a single list with minimal comparisons

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related