Return to Question

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?

I was told it takes:

$$2(n-2) + 1 = 2n-3$$

However, I can't seem to figure out why.

The way to merge them I was thinking just to merge two of the lists, and then merge that big 2/3 list with the remaining list. How come the worst case of that 2n-3?

The complete explanation I was given was:

The worst case occurs if the first list empties when there is exactly 1 item in each of the other two. Prior to this, each of the other n−2 numbers requires 2 comparisons before going into the big list. After this, we only need 1 more comparison between the 2 leftover items.

Which doesn't make complete sense to me. Not sure if its just the grammar of the sentences, but not sure where the $2(n-2)$ came from... What does:

The worst case occurs if the first list empties when there is exactly 1 item in each of the other two.

even mean?

When it says "prior to this", its not clear to me what exactly happened before hand...

What does the "big list" referring to? How did we even get a "big list"?

Btw, I am not looking for an asymptotic answer.

I was also interested in the generalization of my question though:

Extending my question, if we extend merge sort algorithm but instead of 2, to divide by some constant c, why would the recurrence be of the form:

$$T(n) = cT \left( \frac{n}{c} \right) + \left[ (c-1)(n-(c-1)) + \sum^{c-2}_{i=1} i\right]$$

The extra term for merging is not entirely clear to me.

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3)

I was told it takes:

$$2(n-2) + 1 = 2n-3$$

However, I can't seem to figure out why.

The way to merge them I was thinking just to merge two of the lists, and then merge that big 2/3 list with the remaining list. How come the worst case of that 2n-3?

The complete explanation I was given was:

The worst case occurs if the first list empties when there is exactly 1 item in each of the other two. Prior to this, each of the other n−2 numbers requires 2 comparisons before going into the big list. After this, we only need 1 more comparison between the 2 leftover items.

Which doesn't make complete sense to me. Not sure if its just the grammar of the sentences, but not sure where the $2(n-2)$ came from... What does:

The worst case occurs if the first list empties when there is exactly 1 item in each of the other two.

even mean?

When it says "prior to this", its not clear to me what exactly happened before hand...

What does the "big list" referring to? How did we even get a "big list"?

Btw, I am not looking for an asymptotic answer.

I was also interested in the generalization of my question though:

Extending my question, if we extend merge sort algorithm but instead of 2, to divide by some constant c, why would the recurrence be of the form:

$$T(n) = cT \left( \frac{n}{c} \right) + \left[ (c-1)(n-(c-1)) + \sum^{c-2}_{i=1} i\right]$$

The extra term for merging is not entirely clear to me.

How many comparisons in the worst case, does it take to merge 3 lists of size n/3 (its fair to assume these lists are sorted)?

I was told it takes:

$$2(n-2) + 1 = 2n-3$$

However, I can't seem to figure out why.

The way to merge them I was thinking just to merge two of the lists, and then merge that big 2/3 list with the remaining list. How come the worst case of that 2n-3?

The complete explanation I was given was:

The worst case occurs if the first list empties when there is exactly 1 item in each of the other two. Prior to this, each of the other n−2 numbers requires 2 comparisons before going into the big list. After this, we only need 1 more comparison between the 2 leftover items.

Which doesn't make complete sense to me. Not sure if its just the grammar of the sentences, but not sure where the 2*(n-2) came from...

Btw, I am not looking for an asymptotic answer.

I was also interested in the generalization of my question though:

Extending my question, if we extend merge sort algorithm but instead of 2, to divide by some constant c, why would the recurrence be of the form:

$$T(n) = cT \left( \frac{n}{c} \right) + \left[ (c-1(n-(c-1)) + \sum^{c-2}_{i=1} i\right]$$

The extra term for merging is not entirely clear to me.

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?

I was told it takes:

$$2(n-2) + 1 = 2n-3$$

However, I can't seem to figure out why.

The way to merge them I was thinking just to merge two of the lists, and then merge that big 2/3 list with the remaining list. How come the worst case of that 2n-3?

The complete explanation I was given was:

The worst case occurs if the first list empties when there is exactly 1 item in each of the other two. Prior to this, each of the other n−2 numbers requires 2 comparisons before going into the big list. After this, we only need 1 more comparison between the 2 leftover items.

Which doesn't make complete sense to me. Not sure if its just the grammar of the sentences, but not sure where the $2(n-2)$ came from... What does:

The worst case occurs if the first list empties when there is exactly 1 item in each of the other two.

even mean?

When it says "prior to this", its not clear to me what exactly happened before hand...

What does the "big list" referring to? How did we even get a "big list"?

Btw, I am not looking for an asymptotic answer.

I was also interested in the generalization of my question though:

Extending my question, if we extend merge sort algorithm but instead of 2, to divide by some constant c, why would the recurrence be of the form:

$$T(n) = cT \left( \frac{n}{c} \right) + \left[ (c-1)(n-(c-1)) + \sum^{c-2}_{i=1} i\right]$$

The extra term for merging is not entirely clear to me.

How many comparisons in the worst case, does it take to merge 3 lists of size n/3 (its fair to assume these lists are sorted)?

I was told it takes:

$$2(n-2) + 1 = 2n-3$$

However, I can't seem to figure out why.

The way to merge them I was thinking just to merge two of the lists, and then merge that big 2/3 list with the remaining list. How come the worst case of that 2n-3?

Btw, I am not looking for an asymptotic answer.

How many comparisons in the worst case, does it take to merge 3 lists of size n/3 (its fair to assume these lists are sorted)?

I was told it takes:

$$2(n-2) + 1 = 2n-3$$

However, I can't seem to figure out why.

The way to merge them I was thinking just to merge two of the lists, and then merge that big 2/3 list with the remaining list. How come the worst case of that 2n-3?

The complete explanation I was given was:

The worst case occurs if the first list empties when there is exactly 1 item in each of the other two. Prior to this, each of the other n−2 numbers requires 2 comparisons before going into the big list. After this, we only need 1 more comparison between the 2 leftover items.

Which doesn't make complete sense to me. Not sure if its just the grammar of the sentences, but not sure where the 2*(n-2) came from...

Btw, I am not looking for an asymptotic answer.

I was also interested in the generalization of my question though:

Extending my question, if we extend merge sort algorithm but instead of 2, to divide by some constant c, why would the recurrence be of the form:

$$T(n) = cT \left( \frac{n}{c} \right) + \left[ (c-1(n-(c-1)) + \sum^{c-2}_{i=1} i\right]$$

The extra term for merging is not entirely clear to me.