- #1

- 142

- 1

## Homework Statement

Maximum no. of comparisons required to merge two sorted files of length 'm' and 'n' is..

## Homework Equations

## The Attempt at a Solution

I think m+n-1

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter 22990atinesh
- Start date

- #1

- 142

- 1

Maximum no. of comparisons required to merge two sorted files of length 'm' and 'n' is..

I think m+n-1

- #2

- 18,512

- 8,416

Please also provide the reasoning behind your attempt.I think m+n-1

- #3

- 142

- 1

Suppose we have two list LIST-1 & LIST-2 of sorted integers of size 3, 2 respectively (say)

1. First we compare ##1^{st}## element of the both list and suppose we get minimum value from LIST-1, So we store it in the new array. Now we are having two lists of size 2, 2 (1 Comparison)

2. Now we compare ##2^{nd}## element of LIST-1 with ##1^{st}## element of LIST-2 this time element from LIST-2 becomes minimum, So we store it . Now we are having two list of size 2, 1 (1 Comparison)

3. Now we compare ##2^{nd}## element of LIST-1 with ##2^{nd}## element of LIST-2 this time element from LIST-1 becomes minimum, So we store it . Now we are having two list of size 1, 1 (1 Comparison)

4. Now we compare ##3^{rd}## element of LIST-1 with ##2^{nd}## element of LIST-2 this time element from LIST-2 becomes minimum. so we store it . Now we are having two list of size 1, 0 (1 Comparison)

5. Now we store last element left from LIST-1 to the array. Hence 3+2-1 = 4 comparisons

- #4

rcgldr

Homework Helper

- 8,782

- 573

- #5

- 142

- 1

What I'm missing here

Suppose we have two list LIST-1 & LIST-2 of sorted integers of size 3, 2 respectively (say)

1. First we compare ##1^{st}## element of the both list and suppose we get minimum value from LIST-1, So we store it in the new array. Now we are having two lists of size 2, 2 (1 Comparison)

2. Now we compare ##2^{nd}## element of LIST-1 with ##1^{st}## element of LIST-2 this time element from LIST-2 becomes minimum, So we store it . Now we are having two list of size 2, 1 (1 Comparison)

3. Now we compare ##2^{nd}## element of LIST-1 with ##2^{nd}## element of LIST-2 this time element from LIST-1 becomes minimum, So we store it . Now we are having two list of size 1, 1 (1 Comparison)

4. Now we compare ##3^{rd}## element of LIST-1 with ##2^{nd}## element of LIST-2 this time element from LIST-2 becomes minimum. so we store it . Now we are having two list of size 1, 0 (1 Comparison)

5. Now we store last element left from LIST-1 to the array. Hence 3+2-1 = 4 comparisons

- #6

rcgldr

Homework Helper

- 8,782

- 573

- #7

- 142

- 1

Your above approach also ends up with ##m+n-1## comparisons.

- #8

rcgldr

Homework Helper

- 8,782

- 573

Share:

- Last Post

- Replies
- 7

- Views
- 213