• Mood:
• Music:

# Everything you know is wrong.

Question: What is the data structure used in a mergesort?

False Answer: It's an array. I believed this until today, when I finally gave up on an array-based implementation that Just. Would. Not. Work.

True Answer: The only operations you ever perform on a sub-array are append to back, remove from front, and compare front. Mergesort really operates on a queue, or more precisely N queues.

The following C++ sorts an array by dividing it into one-element queues and then merging them:

```//Queue-based mergesort by Brent Royal-Gordon, 2002.
//This code is in the public domain.

template <class T>
void Sort::Merge<T>::sort_plain(T a[], int l) {
Queue::Queue<T> *queue=merge(a, 0, l-1);

for(int c=0; c < l && bool(*queue); c  ) {
a[c]=queue->retrieve();
}

delete queue;
}

template <class T>
Queue::Queue<T> *merge(T a[], int L, int R) {
Queue::Queue<T> *ret=new Queue::Queue<T>;
int length=R-L 1;

if(length == 1) {
ret->append(a[L]);
}
else {
int half=(length / 2)   L-1;
Queue::Queue<T> *left=merge(a, L, half);
Queue::Queue<T> *right=merge(a, half 1, R);

while(*left || *right) {
Queue::Queue<T> *source;

if(!*left) {
source=right;
}
else if(!*right) {
source=left;
}
else {
/* if left > right */
if(comparator(cbdata, &(left->peek()),
&(right->peek())) == 1) {
source=right;
}
else {
source=left;
}
}

ret->append_node(source->retrieve_node());
}

delete left;
delete right;
}

return ret;
}```
Except for some tweaking of the code to calculate `half`, it ran perfectly the first time. Nifty, ne?
• Post a new comment

#### Error

default userpic