1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Maximum number of comparisons required to merge two sorted files

Tags:
  1. Jan 6, 2015 #1
    1. The problem statement, all variables and given/known data
    Maximum no. of comparisons required to merge two sorted files of length 'm' and 'n' is..

    2. Relevant equations


    3. The attempt at a solution
    I think m+n-1
     
  2. jcsd
  3. Jan 6, 2015 #2

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Please also provide the reasoning behind your attempt.
     
  4. Jan 6, 2015 #3
    @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
     
  5. Jan 6, 2015 #4

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  6. Jan 7, 2015 #5
    What I'm missing here
     
  7. Jan 7, 2015 #6

    rcgldr

    User Avatar
    Homework Helper

    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?
     
  8. Jan 10, 2015 #7
    Your above approach also ends up with ##m+n-1## comparisons.
     
  9. Jan 11, 2015 #8

    rcgldr

    User Avatar
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Maximum number of comparisons required to merge two sorted files
  1. Merge sort (Replies: 1)

Loading...