Search code examples
algorithmmergesort

why isn't merge sort O(N^2)? please look at this example


A bubble sort of 16 elements takes 15 steps of 2-2 comparison to sort them one by one.

A merge sort firstly divide them into 16 elements, and merge 2 each time, but the overall steps is still 15 if you draw the picture, i.e. 8+4+2+1=15 in such case, merge cost O(n) while 2-2 comparison cost O(n) so should be O(n^2). why is it false?


Solution

  • Merge sort has a time complexity of O(n log n).

    It's easier to confirm this by closely inspecting the iterative implementation you've described. The algorithm scans the list log(n) times. In your example, it merges every pair, then every four, then every eight, then all sixteen, bringing it to a total of 4 = log2(16) iterations. Since the list itself is length n, the total time complexity is in the order of n log(n), which is validated by calculating that 64 elements in total are iterated by scanning a list of 16 items 4 times.

    The fault in your analysis is incorrectly assuming that every merge is performed with a time complexity of O(n). The time complexity of each merge in a merge sort cannot trivially be represented in terms of n.