Thread: merge sort over (doubly) linked lists

I'm having some trouble with my merge sort routines.

I tried to implement some pseudo-code I found on Wikipedia thats supposed to be optimized for tape drives(since tape drives have the same strengths as a list), but it doesn't seem to change the order at all.

Because of this I have a feeling it will be very obvious but I cant see the problem for the life of me.

Thanks

Code:

void mergeClauses(struct clause_t *left, struct clause_t *right, 
		  struct clause_t **output) {
	bool t1, t2;
	struct clause_t *node;
	struct clause_t *l = left;
	struct clause_t *r = right;

	do {
		if(l->numConflicts >= r->numConflicts) {
			node = l;
			l = l->next;
			addClause(output, removeClause(&left, node));
		} else  {
			node = r;
			r = r->next;
			addClause(output, removeClause(&right, node));
		}

		if(l->next != NULL)
			t1 = (l->numConflicts) > (l->next->numConflicts); 
		else
			t1 = false;
		if(r->next != NULL)
			t2 = (r->numConflicts) > (r->next->numConflicts); 
		else
			t2 = false;
	} while(t1 && t2);

	if(t1 == true)
		addClause(output, removeClause(&left, l));
	if(t2 == true)
		addClause(output, removeClause(&right, r));
}

void sortClauses(struct clause_t **clauses) {
	struct clause_t *input = *clauses; 
	struct clause_t *output = NULL;
	struct clause_t *tapeC = NULL;
	struct clause_t *tapeD = NULL;

	while(input != NULL) {
		while(input != NULL) {
			mergeClauses(input, output, &tapeC);	
			mergeClauses(input, output, &tapeD);	
		}

		while(tapeC != NULL || tapeD != NULL) {
			mergeClauses(tapeC, tapeD, &output);
			mergeClauses(tapeC, tapeD, &input);
		}
	}

	*clauses = output;
}

I decided I didn't really like Wikipedia's idea so I attempted something more straightforward. It just seemed overkill.

Still doesn't work unfortunately. The list never seems to change order.

Code:

void mergeClauses(struct clause_t *l, struct clause_t *r, 
		  struct clause_t **output) {
	while(l != NULL || r != NULL) {
		if(l != NULL) {
			if(r != NULL) {
				if(l->numConflicts <= r->numConflicts)
					addClause(output, popClause(&l));
				else
					addClause(output, popClause(&r));
			} else {
				addClause(output, popClause(&l));
			}
		} else {
			if(r != NULL)
				addClause(output, popClause(&r));
		}
	}
}

void sortClauses(struct clause_t **input) {
	struct clause_t *c;
	struct clause_t *left = NULL; 
	struct clause_t *right = NULL;

	/* Base cases */
	if(*input == NULL)
		return;
	if((*input)->next == NULL)
		return;
	
	/* Divide */
	while(true) {
		c = popClause(input);
		if(c != NULL)
			addClause(&left, c);
		else
			break;

		c = popClause(input);
		if(c != NULL)
			addClause(&right, c);
		else
			break;
	}

	/* Recurse */
	sortClauses(&left);
	sortClauses(&right);
	mergeClauses(left, right, input);
}

Originally Posted by zxcv

I decided I didn't really like Wikipedia's idea so I attempted something more straightforward. It just seemed overkill.

Hint: Cut and Paste code almost always leads to more problems than it solves.