?

Log in

No account? Create an account

Previous Entry | Next Entry

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?