Notices
Results 1 to 2 of 2

Thread: merge sort run time?

  1. #1 merge sort run time? 
    New Member
    Join Date
    Mar 2014
    Posts
    1
    I am confused as to why merging for a list of size 2^k=n takes n steps.

    If you have n=4 lists 3,9,8,10 and you sort from least to greatest:
    3 9 8 10
    (3,9) (8,10) 2 work to compare 3 with 9 and 8 with 10.
    (3,8,9,10) 3 work to compare 3 with 8, 8 with 9, and 9 with 10.

    That's a total of 5 work, not 4. Every definition out there says it takes 4 steps to merge when it obviously takes 5 steps in the example given. Why is that?


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Can you point to a definition that says it should take 4 steps? Merge sort is O(n log n), which should be about 8 for n=4, but big-O notation hides a lot of little details.


    Reply With Quote  
     

Similar Threads

  1. Our transformed concepts If time were to run in reverse.
    By ThinkTank in forum General Discussion
    Replies: 3
    Last Post: January 10th, 2012, 02:53 AM
  2. When Black Holes Merge - A New Line of Thought
    By DaddyUnit in forum Pseudoscience
    Replies: 0
    Last Post: March 19th, 2011, 11:41 AM
  3. Count Sort
    By johnseito in forum Computer Science
    Replies: 0
    Last Post: June 10th, 2010, 04:39 PM
  4. Merge Sort
    By nomo1994 in forum Computer Science
    Replies: 5
    Last Post: February 24th, 2007, 04:41 PM
  5. Coin sort.
    By in forum Mathematics
    Replies: 19
    Last Post: September 10th, 2006, 03:28 AM
Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •