Preface:

I do not care about the viability of my particular merge sort algorithm. That is not what the question is about. I am curious as to why the program I have already written behaves the way it does, not about why I should use the STL or whatever. This is for learning purposes.

Question:

I have a linked list struct composed of Node*s. I've written up a semi-recursive merge sort algorithm (I say semi because the actual sorting is iterative technically) for this particular structure, and it doesn't quite work the way it should (sort ascending). When walking through the code with a debugger, it appears the actual sorting function merge() doesn't retain the newly sorted list throughout calls, and I cannot wrap my brain around how to do that. Could someone explain?

Here is a minimal reproducible example:

#include <iostream>
struct Link {
    Link(int d=int(), Link* n=nullptr) {
        data = d;
        next = n;
    }
    int         data;
    Link* next;
};

struct LinkList {
  Link* sentinel;
  size_t      size;

 LinkList(Link* h=new Link, size_t s=0) {
    size = s;
    sentinel = h;
  }

  ~LinkList() {
    Link* current = sentinel;
    while (current != 0) {
      Link* next = current->next;
      delete current;
      current = next;
    }
    sentinel = 0;
  }
};

// split into beg and end subLinkList using f/s ptr algorithm
void split(Link* sentinel, Link*& beg, Link*& end) {
    Link* s = sentinel, * f = sentinel->next;

    while (f != NULL) {
        f = f->next;
        if (f != NULL) {
            s = s->next;
            f = f->next;
        }
    }
    beg = sentinel;
    end = s->next;
    s->next = NULL;
}

// conquer (merge) elements from both subLinkLists into new sentinel
Link* merge(Link* beg, Link* end) {
    Link* sentinel = new Link;
    Link* tmp;
    for (tmp = sentinel; beg != NULL && end != NULL; tmp = tmp->next) {
        if (beg-> data < end->data) {
            tmp->next = beg;
            beg = beg->next;
        }
        else {
            tmp->next = end;
            end = end->next;
        }
    }
    if (beg == NULL)
        tmp->next = end;
    else
        tmp->next = beg;
    return tmp;
}

// recursive splitting and merging
Link* sort_merge(Link* sentinel) {
    Link* beg, * end;

    if (sentinel == NULL || sentinel->next == NULL)
        return sentinel;

    split(sentinel, beg, end);
    sort_merge(beg);
    sort_merge(end);

    return merge(beg, end);
}

// helper function calls sort_merge
void sort(LinkList &l) {
  sort_merge(l.sentinel);
}

void print(LinkList &l) {
  for (Link* n = l.sentinel; n != NULL; n = n->next) {
      std::cout << n->data << '\n';
    }
}

int main() {
  // set up linked LinkList 5->4->3->2->1->nullptr
  Link* sentinel = new Link(5 , new Link(4, new Link(3, new Link(2, new Link(1)))));
  LinkList l(sentinel,5);

  sort(l);
  print(l);

  return 0;
}

The output I want to have is

1
2
3
4
5

but it outputs

5

CodePudding user response：

A few issues:

1. merge returns the last node of merged list instead of the first. So change:

   return tmp;
   

   to:

   return head->next;
   

2. In msort the return value of the recursive call is ignored, but it is important, as it represents the first node after the sort operation. So change:

   msort(left);
   msort(right);
   

   to:

   left = msort(left);
   right = msort(right);
   

3. In sort the return value of msort is ignored so that the head reference of the list is never updated. So change:

   msort(l.head);
   

   to:

   l.head = msort(l.head);