Brent Dax (brentdax) wrote,
Brent Dax
brentdax

  • 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?
Subscribe

  • Paging madlori (and anyone who knows her)

    An interesting thing just happened on Facebook chat. Lori Summers [2:29:44] Got my message ? Brent Royal-Gordon [2:33:45] I did. Lori Summers…

  • guest post

    kate is the best better than the rest the best the best haikus about kate: kate's my favourite i want to lick her ballsack it would taste so…

  • Practice

    This December, I will have been practicing programming seriously for ten years. That will mark the tenth anniversary of me starting to learn Perl. I…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments