Results 1 to 2 of 2

Math Help - Merge Sort Algorithm

  1. #1
    Newbie
    Joined
    May 2007
    Posts
    23

    Merge Sort Algorithm

    I know that in the worst case the merge sort algorithm takes theta(n lg n) to complete.

    I know that when sorting an array of size 6 the maximum number of comparisons required is 11.

    How can I figure the minimum number of comparisons to sort an array of size 6?

    pwr
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by pwr_hngry View Post
    I know that in the worst case the merge sort algorithm takes theta(n lg n) to complete.

    I know that when sorting an array of size 6 the maximum number of comparisons required is 11.

    How can I figure the minimum number of comparisons to sort an array of size 6?

    pwr
    The minimum number of comparisons occurs when the array is already in
    sorted order. Now look at the tree of splits of the array into sub-arrays
    and count the number of comparisons needed in the merge step when
    the left sub-array contains elements all less than each of the elements of the
    right-sub array.

    If the sub-arrays both contain single elements 1 comparison is made

    If the left sub-array contains 1 element and the right sub-array 2 elements then 1 comparison is made

    If both sub-arrays contain 3 elements then 3 comparisons are needed.

    The merges in the decomposition tree for an array of size 6 is comprised
    of merges from the above list, and by adding up the comparisons for the
    required merges you will get the answer you need.

    (I make it 2 merges of type (1,1), two merges of type (1,2), and one
    merge of type (3,3) to give a total of 7 comparisons).

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. how to merge system of recurrence equations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 28th 2011, 02:01 PM
  2. What sort of DE is this?
    Posted in the Differential Equations Forum
    Replies: 6
    Last Post: November 1st 2010, 02:24 AM
  3. Proof Shuttle Sort is a quadratic order algorithm.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 11th 2010, 12:50 PM
  4. More max/min (sort of)
    Posted in the Calculus Forum
    Replies: 4
    Last Post: October 23rd 2009, 02:39 PM
  5. Sort this numbers
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 23rd 2009, 04:36 AM

Search Tags


/mathhelpforum @mathhelpforum