- #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

- 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

- 16,829

- 6,652

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,728

- 545

- #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,728

- 545

- #7

- 142

- 1

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

- #8

rcgldr

Homework Helper

- 8,728

- 545

- Replies
- 2

- Views
- 802

- Replies
- 14

- Views
- 14K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 0

- Views
- 5K

- Last Post

- Replies
- 6

- Views
- 6K

- Last Post

- Replies
- 1

- Views
- 703

- Last Post

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 0

- Views
- 1K

- Last Post

- Replies
- 4

- Views
- 2K

- Replies
- 2

- Views
- 3K