Maximum number of comparisons required to merge two sorted files

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

Answers and Replies

  • #3
142
1
@Orodruin Please see this question
Capture2.jpg


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
An alternative, list-m and list-n. Assume all but the last element of list-m is smaller than the first element of list-n, that's m-1 comparisons (not including the compare with last element of list-m yet). Assume last element of list-m is greater than all of the elements in list-n, that's n comparisons, and the last element of list-m is copied to the output list, 0 comparisons. The issue is proving there isn't a pattern that produces more compares.
 
  • #5
142
1
An alternative, list-m and list-n. Assume all but the last element of list-m is smaller than the first element of list-n, that's m-1 comparisons (not including the compare with last element of list-m yet). Assume last element of list-m is greater than all of the elements in list-n, that's n comparisons, and the last element of list-m is copied to the output list, 0 comparisons. The issue is proving there isn't a pattern that produces more compares.
What I'm missing here
@Orodruin Please see this question
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
You're not missing anything. The issue here is how do you prove the worst case number of comparasons without going through every possible scenario?
 
  • #7
142
1
An alternative, list-m and list-n. Assume all but the last element of list-m is smaller than the first element of list-n, that's m-1 comparisons (not including the compare with last element of list-m yet). Assume last element of list-m is greater than all of the elements in list-n, that's n comparisons, and the last element of list-m is copied to the output list, 0 comparisons. The issue is proving there isn't a pattern that produces more compares.
You're not missing anything. The issue here is how do you prove the worst case number of comparasons without going through every possible scenario?
Your above approach also ends up with ##m+n-1## comparisons.
 
  • #8
rcgldr
Homework Helper
8,728
545
A logical explanation rather than specific cases would be a better "proof". After each compare, one element is moved from either list-m or list-n. In the worst case scenario, there is 1 element remaining in list-m and 1 element remaining in list-n, and m+n-2 compares have been performed. There is one more compare performed, which moves an element from either list-m or list-n, emptying that list, so the remaining element from the other list is moved without doing any compares, and the worst case scenario is m+n-1 compares.
 
  • Like
Likes 22990atinesh

Related Threads on Maximum number of comparisons required to merge two sorted files

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
Replies
1
Views
703
Replies
6
Views
2K
Replies
0
Views
1K
  • Last Post
Replies
4
Views
2K
Top