Do you know...

This is a discussion on Do you know... within the C++ Programming forums, part of the General Programming Boards category; [tag] Code: Do you know if Merge Sort is supposed to be quicker than Quick?? Look at the output of ...

  1. #1
    Registered User
    Join Date
    May 2005
    Posts
    3

    Do you know...

    [tag]
    Code:
    Do you know if Merge Sort is supposed to be quicker than Quick??
    Look at the output of my project:
    
    
    
    Sorting in progress: Please wait
    
     ***************************************************
    Sort Type               # of Elements                   Time(s)
    --------                -------------------             -------
    Quick                           5000                    0
    Merge                           5000                    0
    Heap                            5000                    0
    Insertion                       5000                    0.015
    
    Quick                           10000                   0
    Merge                           10000                   0
    Heap                            10000                   0.016
    Insertion                       10000                   0.062
    
    Quick                           15000                   0
    Merge                           15000                   0
    Heap                            15000                   0.016
    Insertion                       15000                   0.156
    
    Quick                           20000                   0
    Merge                           20000                   0
    Heap                            20000                   0
    Insertion                       20000                   0.203
    
    Quick                           25000                   0.016
    Merge                           25000                   0
    Heap                            25000                   0
    Insertion                       25000                   0.313
    
    Quick                           30000                   0.015
    Merge                           30000                   0
    Heap                            30000                   0
    Insertion                       30000                   0.469
    
    Quick                           35000                   0
    Merge                           35000                   0
    Heap                            35000                   0.016
    Insertion                       35000                   0.64
    
    Quick                           40000                   0.016
    Merge                           40000                   0
    Heap                            40000                   0.016
    Insertion                       40000                   0.828
    
    Quick                           45000                   0.015
    Merge                           45000                   0
    Heap                            45000                   0.016
    Insertion                       45000                   1.078
    
    Quick                           50000                   0.016
    Merge                           50000                   0
    Heap                            50000                   0.015
    Insertion                       50000                   1.36
    
    Quick                           55000                   0.015
    Merge                           55000                   0
    Heap                            55000                   0.016
    Insertion                       55000                   1.672
    
    Quick                           60000                   0.015
    Merge                           60000                   0
    Heap                            60000                   0.015
    Insertion                       60000                   2.094
    
    Quick                           65000                   0.015
    Merge                           65000                   0
    Heap                            65000                   0.032
    Insertion                       65000                   2.531
    
    Quick                           70000                   0.016
    Merge                           70000                   0
    Heap                            70000                   0.016
    Insertion                       70000                   2.891
    
    Quick                           75000                   0.016
    Merge                           75000                   0
    Heap                            75000                   0.031
    Insertion                       75000                   3.281
    
    Quick                           80000                   0.015
    Merge                           80000                   0
    Heap                            80000                   0.032
    Insertion                       80000                   4.062
    
    Quick                           85000                   0.016
    Merge                           85000                   0
    Heap                            85000                   0.032
    Insertion                       85000                   4.953
    
    Quick                           90000                   0.015
    Merge                           90000                   0
    Heap                            90000                   0.031
    Insertion                       90000                   6.063
    
    Quick                           95000                   0.016
    Merge                           95000                   0
    Heap                            95000                   0.031
    Insertion                       95000                   7.171
    
    Quick                           100000                  0.032
    Merge                           100000                  0
    Heap                            100000                  0.047
    Insertion                       100000                  8.703
    [/tag]

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,806
    Sorting times for different algorithms are often affected by the data being sorted, i.e. is the data truly random or is it already sorted in ascending/descending order and where average-case/worst-case timing comes into play. You failed to provide any code for us to look at so we can only go by the published performance of the various sorting algorithms. According to the Wikipedia entry:

    Quote Originally Posted by Wikipedia
    Mergesort has an average and worst-case performance of O(n log n). In the worst case, merge sort does about 30% fewer comparisons than quicksort does in the average case; thus merge sort very often needs to make fewer comparisons than quicksort. In terms of moves, merge sort's worst case complexity is O(n log n)--the same complexity as quicksort's best case, and merge sort's best case takes about half as much time as the worst case.

    However, merge sort performs 2n - 1 method calls in the worst case, compared to quicksort's n, thus has roughly twice as much recursive overhead as quicksort. Mergesort's most common implementation does not sort in place, meaning memory the size of the input must be allocated for the sorted output to be stored in. Sorting in-place is possible but requires an extremely complicated implementation.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21