1

Possible Duplicate:
How to sort in-place using the merge sort algorithm?

Usually we take an extra array to sort it using merge sort , is it possible to do this without using extra space ?

If this is possible then merge sort would be better than quick sort right?

Community
  • 1
  • 1
h4ck3d
  • 6,134
  • 15
  • 51
  • 74

1 Answers1

5

Yes, it's possible to perform an in-place merge sort. That does not mean it doesn't require any extra memory, since the recursion still takes O(lg n) stack space (just like quicksort).

Edit: it's been long since I read the Katajainen paper, and I never paid attention to the space complexity claim; apparently, merge sort can be done in O(1) extra space.

But no, all this does not mean one algorithm is better than another, unless you specify what you mean by that word. Randomized quicksort, while it can go quadratic, still performs a smaller expected number of operations, regardless of the input. Which one "works better" for your data depends on factors ranging from the statistics of the data to the hardware the program runs on.

Community
  • 1
  • 1
Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • IIRC the paper I referenced over on that question shows that you can do it genuinely in `O(1)` space, no `O(log N)` stack. It's just slow, `O(N log N)` but with big constants compared to more common sorts. But I haven't re-read it recently. – Steve Jessop Sep 18 '12 at 12:08
  • @SteveJessop: neither have I, but I hedged the answer anyway. – Fred Foo Sep 18 '12 at 12:36
  • @larsmans Talking of `O(1)` extra space, does it include the unit space taken by the variable declared in `for` loop? Just a thought. – CᴴᴀZ Oct 06 '13 at 19:57
  • @ChaZ: yes it does, because the loop variables in this algorithm aren't pointers to variable-size data structures. – Fred Foo Oct 07 '13 at 09:31
  • @larsmans: If such is the case, then having a constant `(k)` no. of `int` type variables in a method will still account to `O(1)` space complexity? – CᴴᴀZ Oct 08 '13 at 14:41
  • 1
    @ChaZ: yes, except in a recursion. – Fred Foo Oct 08 '13 at 15:43