0

I am aware of this Q: inplace_merge: What causes a complexity of N*log(N) vs. N-1?

but I find answer unsatisfactory since part Im really interested in in A is not clearly explained. More specificaly it is not clear (to me :)) why cant inplace_merge do inplace merge without any additional memory in linear time by just starting from begin and when your current item is greater than the one is second range (middle, end) just do a constant time swap.

Community
  • 1
  • 1
NoSenseEtAl
  • 28,205
  • 28
  • 128
  • 277

1 Answers1

3

Imagine you are merging the two sorted sub-sequences:

11, 12, 13, 14     1,  2,  3,  4
^                  ^

1 < 11, so you swap:

 1, 12, 13, 14    11,  2,  3,  4
     ^             ^

11 < 12, swap:

 1, 11, 13, 14    12,  2,  3,  4
         ^         ^

12 < 13, swap:

 1, 11, 12, 14    13,  2,  3,  4
             ^     ^

13 < 14, swap:

 1, 11, 12, 13    14,  2,  3,  4
               ^   ^

You've reached the end of one of the subsequences, so you stop. Is the merged sequence sorted?

Casey
  • 41,449
  • 7
  • 95
  • 125
  • doh! also to insert element from firt range into second you need to do binary search so that explains log n factor... tnx – NoSenseEtAl Jul 10 '13 at 17:47