CODEWITHSUNDEEP
c++mergesortsingly-linked-list
Tanya Tazzy Hegarty
Tanya Tazzy Hegarty

Reputation: 111

Mergesort on a Singly Linked List C++

I am looking for some kind of simple way I can learn and understand merge sort on these. I have looked on the web and it has been found that merge sort is really good for singly linked lists but I cant understand how to do it. This is the websites I found: Wikipedia Merge sort and Specifically linked lists

I am not sure what code to give you. I basically just have this in my header file and am new to this so I am very basic. Thank you for your help in advance :)

class Node
{
public:
    int data;
    Node* next;
    Node()
    {
        next = NULL;
        data = 0;
    }
};

class SLLIntStorage
{
public:
    Node* head;
    Node* current;
    Node* tail;

    void Read(istream&);
    void Write(ostream&);
    void setReadSort(bool);
    void sortOwn();
    void print();

    bool _sortRead;
    int numberOfInts;

    SLLIntStorage(const SLLIntStorage& copying)
    {

    }

    SLLIntStorage(void);
    ~SLLIntStorage(void);
};

Upvotes: 0

Views: 1917

Answers (1)

Harald Scheirich
Harald Scheirich

Reputation: 9764

If you look at this paragraph from wikipedia

Conceptually, a merge sort works as follows

  1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
  2. Divide the unsorted list into two sublists of about half the size.
  3. Sort each sublist recursively by re-applying the merge sort.
  4. Merge the two sublists back into one sorted list.

This tells you pretty succinctly what you need to do and what kind of operations you need. sentences 2 and 4 are operations that you need to be able to do Split() and Merge(). Split could be implemented on your Node class as 

// Split: removes half of the list and returns a pointer to it
Node* Node::Split()
{
}

similarly Merge could be implemented as 

// Merge: insert elements from source in order
Node::Merge(Node* source)
{
}

as a whole 1,2,3,4 describe what you need to do to perform the actual sorting implement these steps in order in the sorting function by using the list operations Merge and Split.

This is only one way Merge and Split could look like, how you implement them will depend on your style, requirements, knowledge of c++ and various other factors. (I am sure you will see some other solutions in the answers). You will probably also need a Node::Append(Node* val) or something similar as a basic operator. It does not look like you will need Node::Remove(Node* val) but it might not hurt to implement that too.

Upvotes: 2

Related Questions