2

It seems that in a lot of text books top down Merge Sort is done with arrays given its advantage of random access.

I am wondering if there is a way of doing Merge Sort with other data structures? Say the data is stored in a queue or a stack, is it possible to do Merge Sort on the queue/stack with at most another auxiliary queue/stack?

My main concern is that since there is no random access, would merge sort in this case still be able to reach O(n logn) efficiency?

Enzo
  • 969
  • 1
  • 8
  • 23
  • You can do merge sort in O(*n* lg *n*) time on a linked list. In fact, it is *the* linked list sorting algorithm, AFAIK. – Fred Foo Mar 16 '13 at 17:50
  • merge sort doesn't need random access, so I'm not sure what's your main concern is... – Karoly Horvath Mar 16 '13 at 17:59
  • @KarolyHorvath but in the array version, splitting the array into halves certainly needs random access right? I mean in a linked list I can use some trick to get to the middle, but that takes O(n) time right? – Enzo Mar 16 '13 at 18:36
  • you only need the number of elements. you process the first half, then the next half.. – Karoly Horvath Mar 16 '13 at 20:03
  • but how would I get the number of elements in a linked list without walking through it first? – Enzo Mar 17 '13 at 00:11
  • [This answer](http://stackoverflow.com/a/18352989/1711796) may help. – Bernhard Barker Aug 21 '13 at 15:11

1 Answers1

0

An additional advantage of using an array with merge sort is that if you write clever (but incomprehensible) algorithm you can switch the "scratch" array and the "real" array between levels of recursive calls. In any implementation of merge sort worth its salt will allocate the "scratch" array only once, but with the switching technique, you only have to move your results at most once.

With stacks and queues you will likely use an array anyway as an underlying data structure. You can use linked lists, but then the constant factors in push() and pop() or enqueue() and dequeue() grow larger, as you'll also have to allocate the memory for your items. Clearly, as @LearnedfromMistake shows, using stacks and queues is possible, but given that arrays are likely to be used as an underlying data structure anyway, it is not clear what the advantage of such an approach would be.

angelatlarge
  • 4,086
  • 2
  • 19
  • 36