Jump to content

Merge sort run time


DylsexicChciken

Recommended Posts

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 by DylsexicChciken
Link to comment
Share on other sites

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 account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.