1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Why is mege sort O(n log n)?

Discussion in 'C' started by Whilliam, Oct 5, 2010.

  1. Whilliam

    Whilliam New Member

    Oct 5, 2010
    Likes Received:
    Trophy Points:
    Example, n is 8.
    Merge sort (for link list) is constantly divide the list into two sublist until every node->next will point to null. Then, sort them by merging them.

    When I tried to count it myself, in the divide part
    first divide the 8 nodes into two. In link list, you will need to traverse. Since traversing in merge sort is n/2, I will have 4 traversals.
    After dividing the 8 nodes into two, I will divide the left sublist (which has 4) and the right sublist (which also has 4) into two. The left sublist will have 2 traversal, as well as the right sublist.
    Sum it all up, it will be O(8).
    Then, divide the 4 groups of 2 into half, we will add 4 to O(8).
    So technically, it's O(12) in the divide part.
    Then in the merge part, it's actually the same.
    So it should be O((n + 4)*(n + 4)).
    Can anyone explain to me why merge sort is O(n log n)?
  2. techgeek.in

    techgeek.in New Member

    Dec 20, 2009
    Likes Received:
    Trophy Points:
    EOC (exploitation of computers)..i m a Terminator.
    Not an alien!! for sure
    Home Page:

Share This Page