DylsexicChciken Posted March 22, 2014 Share Posted March 22, 2014 (edited) 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, 2014 by DylsexicChciken Link to comment Share on other sites More sharing options...
DylsexicChciken Posted March 22, 2014 Author Share Posted March 22, 2014 (edited) 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, 2014 by DylsexicChciken Link to comment Share on other sites More sharing options...
mathematic Posted March 22, 2014 Share Posted March 22, 2014 Best case is O(n) not n. In general it is O(nlogn). http://en.wikipedia.org/wiki/Sorting_algorithm Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now