How can I write merge-sort function that takes LinkedList& as input in C++?

Question

Here is a declaration of my LinkedList:

struct LinkedList {
LinkedListNode *head, *tail;
LinkedList() { head = tail = NULL; }
~LinkedList() {
    Clear();
} //end-~LinkedList

void Clear() {
    while (head) {
        LinkedListNode* p = head;
        head = head->next;
        delete p;
    } //end-while

    head = tail = NULL;
} //end-Clear

void Append(int key) {
    LinkedListNode* node = new LinkedListNode(key);
    if (tail == NULL) head = tail = node;
    else {
        tail->next = node;
        tail = node;
    } //end-else
} //end-Append
};

Here is function body that I need to implement as this format in C++:

void MergeSort(LinkedList& list){ //I need to make merge sort with LinkedList }

Here is code that testing my sort algorithms, but merge sort does not work (by the way I can't change test side).

#define N 1024*32
int A[N];  
typedef void (*SortingFunction)(LinkedList &);

float Test(SortingFunction F, char *msg){
  int B[] = {4, 2, 5, 7, 8, 1, 10, 9, 15, 34, 6, 17, 66, 55, 44, 33};

  LinkedList list;
  for (int i = 0; i < sizeof(B) / sizeof(int); i++) {
      list.Append(B[i]);
  } //end-for

  // Use the sorting algorithm
  F(list);

  printf("Using %s to sort %d numbers...\n", msg, 16);

  // Check the result
  LinkedListNode* p = list.head;
  int S[] = { 1, 2, 4, 5, 6, 7, 8, 9, 10, 15, 17, 33, 34, 44, 55, 66 };
  for (int i = 0; i < sizeof(S) / sizeof(int); i++) {
      if (S[i] != p->key) return 0;
      p = p->next;
  } // end-for

  list.Clear();
  srand((unsigned int)time(NULL));
  int i;
  int min = INT_MAX;
  int max = 0;
  for (i=0; i<100;i++){
      int number = rand();
      list.Append(number);

      if (number<min) min=number;
      else if (number>max) max=number;
  } //end-for

  printf("Using %s to sort %d numbers...", msg, N);
  time_t t1 = time(NULL);
  F(list);
  time_t t2 = time(NULL);
  printf("took %I64d seconds\n", t2-t1);

  // Check the result
  if (list.head->key!=min || list.tail->key!=max) return 0;

  LinkedListNode* q = list.head;
  p = q->next;
  while (p){
    if (q->key > p->key) return 0;
    q = p;
    p = p->next;
  } //end-for

  return 100;
} //end-Test

/****************************************************
 * Main function
 ****************************************************/
int main(){
  float grade = 0;
  printf("======================= TEST4 =======================\n");
  grade += Test(MergeSort, "MergeSort");
  return 0;
} //end-main

Here is code that I wrote for merge sorting but it's not working, I think problem is function prototype. All of example that I have seen from internet using node pointer as function parameter. But in mine I have to pass reference as LinkedList&. I try some of codes but I couldn't achieve to get result. Also, here is code that I try but didn't get result.

void MergeSort(LinkedList& list){
    LinkedListNode* myhead = list.head;
    mergeSorting(myhead);

} //end-MergeSort
void mergeSorting(LinkedListNode*& head) {
    if (head->next != NULL)             
    {
        LinkedListNode* head1;
        LinkedListNode* head2 = head;
        int len = getLength(head);
        for (int i = 0; i < len / 2; i++)
        {
            head1 = head2;
            head2 = head2->next;
        }
        head1->next = NULL; 
        head1 = head;
        mergeSorting(head1);
        mergeSorting(head2);
        head = merge(head1, head2);
    }
}
int getLength(LinkedListNode* head) {
    LinkedListNode* cur = head;
    int i = 0;
    for (; cur != NULL; cur = cur->next) {
        i++;
    }
    return i;
}
LinkedListNode* merge(LinkedListNode*& head1, LinkedListNode*& head2) {
    LinkedListNode* newHead;
    if (head1 == NULL) return head2;
    else if (head2 == NULL) return head1;
    if (head1->key < head2->key) {
        newHead = head1;
        newHead->next = merge(head1->next, head2);
    }
    else {
        newHead = head2;
        newHead->next = merge(head1, head2->next);
    }
    return newHead;
}

Can you show the code you've already written, and explain how exactly your program doesn't work or doesn't produce the expected results? You have to show your work first; it must meet all requirements for a [mre]; and it must be a good-faith real attempt to implement your program and not a few token lines of code, before asking for help on stackoverflow.com. We don't write entire programs, or functions, for other people, here. For more information, see [ask] questions, take the [tour], and read the [help]. — Sam Varshavchik, Apr 10 '20 at 03:25
You could copy the node data to an array or other container, merge sort that container, and then rebuild a new list with the sorted container. You still have to implement the merge sort, but it would be easier to do when dealing with arrays instead of a linked list (and especially a singly linked list). — PaulMcKenzie, Apr 10 '20 at 03:29
I updated to post to make it easier to understand. I am thankful for your answers. You both are such a kind person. But I try many things to do I could not handle. — markus, Apr 10 '20 at 03:49
@yfy What do you mean by "not available"? You say you can't change the test side, but what I suggested if purely within the implementation. You originally posted a blank function, so the assumption made was that you could take that list, just copy the data, sort it "easily", and then just copy the sorted back to the list. The array is internal within the sort function, so it is all an implementation detail that shouldn't affect the client code calling the mergesort function. At the end, all the client will see is a sorted linked list, and isn't that the goal? — PaulMcKenzie, Apr 10 '20 at 04:15
As to searching the internet for merge sort code, [you can read this](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). — PaulMcKenzie, Apr 10 '20 at 04:18
[C++ Implementation of Mergesort of Linked-List](https://stackoverflow.com/q/57735047/3422102) may also be helpful (see final comment after Answer for solution) — David C. Rankin, Apr 10 '20 at 05:00
The test in `merge` should be `if (head1->key <= head2->key)` to preserve stability, furthermore there is no need to pass the arguments by reference to this function. Just use `LinkedListNode* merge(LinkedListNode* head1, LinkedListNode* head2)` — chqrlie, Apr 10 '20 at 12:47
@PaulMcKenzie I agree with you but the man who gave this task to me said that array I don't want array implementation, I will review it. So I cant use array implementation even inside of the function. — markus, Apr 10 '20 at 13:01
@yfy: you can accept one of the answers by clicking on the grey checkmark below its score — chqrlie, Apr 10 '20 at 19:27

score 2 · Answer 1 · answered Apr 10 '20 at 06:39

The code needs a slightly different approach. mergeSorting should take a pointer to node as an input parameter, and return a pointer to node. The last 3 lines should be something like:

        head1 = mergeSorting(head1);
        head2 = mergeSorting(head2);
        return merge(head1, head2);

Then for the calling code:

void MergeSort(LinkedList& list){
    list.head = mergeSorting(list.head);
}

Assuming you're allowed to do a web search for example algorithms, a bottom up merge sort for linked lists is faster, but it's not based on the logic used for a bottom up merge sort for arrays. If interested, the wiki article has example pseudo code:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

I got the error, sir, about stack overflow in the merge function. Unhandled exception at 0x00711590 in Sorting.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00722FFC). — markus, Apr 10 '20 at 13:15
@yfy - using a recursive merge() function will result in stack overflow for large lists. Change it to use a loop instead. I'm not sure why it failed with just 100 nodes, unless you changed the code to sort a larger list. — rcgldr, Apr 10 '20 at 16:53

chqrlie · Answer 2 · 2020-04-10T20:51:48.830

You tend to use references in places where they create confusion.

MergeSort should just take a pointer to the first node of the list and return a pointer to the first node of the sorted list.

merge should just take 2 pointers to initial nodes of sorted lists and return a pointer to the first node of the merged sorted list.

Here is a modified version:

void MergeSort(LinkedList& list) {
    LinkedListNode *cur = list.head = mergeSorting(list.head);
    if (cur) {
        while (cur->next)
            cur = cur->next;
    }
    list.tail = cur;
}
LinkedListNode *mergeSorting(LinkedListNode *head) {
    if (head->next != NULL) {
        LinkedListNode *head1;
        LinkedListNode *head2;
        LinkedListNode *prev = head;
        LinkedListNode *cur = head;
        int half = getLength(head) / 2;
        for (int i = 0; i < half; i++) {
            prev = cur;
            cur = cur->next;
        }
        prev->next = NULL; 
        head1 = mergeSorting(head);
        head2 = mergeSorting(cur);
        head = merge(head1, head2);
    }
    return head;
}
int getLength(const LinkedListNode *head) {
    const LinkedListNode* cur = head;
    int i = 0;
    for (; cur != NULL; cur = cur->next) {
        i++;
    }
    return i;
}
LinkedListNode *merge(LinkedListNode *head1, LinkedListNode *head2) {
    LinkedListNode *newHead;
    if (head1 == NULL)
        return head2;
    if (head2 == NULL)
        return head1;
    if (head1->key <= head2->key) {
        newHead = head1;
        newHead->next = merge(head1->next, head2);
    } else {
        newHead = head2;
        newHead->next = merge(head1, head2->next);
    }
    return newHead;
}

Sir, Thank you for your interest. I formated code as you show but I got some of the errors about the unresolved external symbol from the compiler. ---> Severity Code Description Project File Line Suppression State Error LNK2001 unresolved external symbol "int __cdecl getLength(struct LinkedListNode *)" (?getLength@@YAHPAULinkedListNode@@@Z) 1 — markus, Apr 10 '20 at 14:00
I changed the prototype of the `getLength()` function, declaring the pointer argument as `const`. Either update the prototype in the header file o remove the `const` keywords in the function definition. — chqrlie, Apr 10 '20 at 14:37
I am thankful to you this code is working well but how can I assign list.tail in this approach. — markus, Apr 10 '20 at 20:06
@yfy: Good point. The simplest solution is adding an extra pass to find the last node. Technically it should be feasible to keep track of the last node during the merging phases, but the extra book-keeping might cost more then this final scan. — chqrlie, Apr 10 '20 at 20:09

How can I write merge-sort function that takes LinkedList& as input in C++?

2 Answers2