Merge sort on a linked list

Temujin_12 · #1 01-Oct-2003, 16:57

I'm fairly new at C++ (but not programming). I'm trying to do a merge sort on a linked list (I wrote). The linked list works just fine (I can print it out unsorted and add objects just fine). I wrote a merge sort in Java that works just fine.

Here's the working code for the Java merge sort:

JAVA Code:

public node merge_sort (node list1) {
	if (list1 == null || list1.next == null)
           return list1; // checks for empty or single list
	node list2 = split (list1);
	list1 = merge_sort (list1);
	list2 = merge_sort (list2);
	return merge (list1, list2);
} // end merge_sort

public node split (node list1) {
	if (list1 == null || list1.next == null) return null;
	node list2 = list1.next;
	list1.next = list2.next;
	list2.next = split (list2.next);
	return list2;
} // end split method

public node merge (node list1, node list2) {
	if (list1 == null) return list2;
	if (list2 == null) return list1;
	if (list1.student.id < list2.student.id) {
		list1.next = merge (list1.next, list2);
		return list1;
	} // end if
	else {
		list2.next = merge (list1, list2.next);
		return list2;
	} // end else
} // end merge method

What I did was copy the code from this and change the syntax to C++. The first time I did, it compiled but I was passing things by value so when I returned from the recursion none of the changes were saved. So I went through and changed things so they passed by reference instead. But this code has a few return type errors:

CPP / C++ / C Code:

void sort (bool i, bool r, bool n) {
    ins = i; // this booleans are to be used for search options
    rev = r;
    num = n;
    head = merge_sort (head);
} // end sort function

line merge_sort (line &list1) {
    if (&list1 == NULL || &list1.next == NULL)
      return list1;
    line list2 = split (list1);
    list1 = merge_sort (list1);
    list2 = merge_sort (list2);
    return merge (list1, list2);
} // end merge_sort function

line split (line &list1) {
    if (&list1 == NULL) return list1;
    if (&list1.next == NULL) return *list1.next;

    line list2 = *list1.next;
    list1.next = list2.next;
    list2.next = split (list2.next);
    return list2;
} // end split function

line merge (line &list1, line &list2) {
    if (&list1 == NULL) return list2;
    if (&list2 == NULL) return list1;
    // 'col' is the variable we're sorting on
    if (list1.col < list2.col) {
      list1.next = merge (list1.next, list2);
      return list1;
    } // end if
    else {
      list2.next = merge (list1, list2.next);
      return list2;
    } // end else
} // end merge function

So my question is how do I fix the return type errors and make sure that I am actually changing the pointers in the list and not just copies of them?

Any help would be greatly appriciated.

Peter_APIIT · #2 06-Mar-2008, 20:33

What is your logic of this program ?

Thanks.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Merge sort on a linked list

Re: Merge sort on a linked list