I am confused as to why merge sort for a list of size 2^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?

Edited March 22, 201411 yr by DylsexicChciken

Edit, first line should read: I am confused as to why merge sort for a list of size 2^k=n takes n steps.

Edited March 22, 201411 yr by DylsexicChciken

Best case is O(n) not n. In general it is O(nlogn).

 

http://en.wikipedia.org/wiki/Sorting_algorithm