Thread: merge sort on linked list

1. 479
posts
the unafork bomber

merge sort on linked list

does anyone know or have any tips on using the mergesort algorithm on a linked list ?
I've looked up on goodle and didnt get much info about it, other than one algorithm i have a hard time understanding

thx

2. i dont see how it's possible. merge sort requires a list be indexed. a linked list per se is not indexed.

3. 479
posts
the unafork bomber
it is possible on doubly linked lists. Thats the only way i got it to work, but after reading and asking around a little, i hear the fastest way to sort a linked list is to sort on insertion in the list. the algorithm is also much simpler

4. 479
posts
the unafork bomber
here is a piece of code pretty usefull for sorting linked lists.

5. 1,839
posts
Registered User
usually a linked list is
Head ->Node->Node->Node->Node->Node->End

For Example (C++ code)
Node.h
Code:
```class node{
public:
node(void);  // constructor
void setData(int);
int getData(void);
void insert(node &);
void printList(void);
private:
int data;
node *next;
};

node::node(void){
next = NULL;
}

void node::setData(int d){
data = d;
}

int node::getData(void){
return data;
}

void node::insert(node &p){
p.next = next;
next = &p;
}

void node::printList(void){
if(next != NULL){
cout << next->data << endl;
next->printList();
}
}```
Main.cpp
Code:
```#include<iostream>
using namespace std;
#include"node.h"

int main(){
node head;
node *p;
int temp;
do{
cout << "Next value (enter 0 when finished): ";
cin >> temp;
if(temp != 0){
p = new node;
p -> setData(temp);
head.insert(*p);
}
}while(temp != 0);
head.printList();
}```
You cannot do a merge sort since like the man said it requires indexes ....

but i guess you could add a (bubble) sort function to your node class and list class or file
Code:
```//add private var int isSet to the class definition as well as the definition for sort
//in your node constructor the set isSet to 0.  in the setData function set isSet = 1

int node::sort(int isChanged){
if(next != NULL){//if next node has data
if(isSet){ // if this node has data
if(data > next->data){//swap nodes
int tempData = data;
data = next->data;
next->data = tempData;
isChanged = 1;
}
}
return next->sort(isChanged);
}else{//if we have reached the end of the list
return isChanged;//return 0 if it has been unchanged 1 if its been changed
}
}```
and then in your main.cpp
Code:
```int isChanged;
do{
isChanged = head.sort(0);//start with is changed = 0 on each loop
}while(isChanged);```
and that will sort your linked list from smallest to largest using a bubble sort

6. You cannot do a merge sort since like the man said it requires indexes ....
You can do a merge sort (saying nothing of efficiency), since you can get the index of a given node by starting at the head and counting the number of nodes that you traverse through.

7. 479
posts
the unafork bomber
yeah you can merge sorts on doubly linked lists, it's just not efficient, and i think the list needs to to be circular.
We had that as an exercise in a exam in school, but the best is to sort as you insert.

but i guess you could add a (bubble) sort function to your node class and list class or file
I'm using C, there are no classes in C (and that's a real bummer).

8. 158
posts
Code Monkey
Originally Posted by eirche
i dont see how it's possible. merge sort requires a list be indexed. a linked list per se is not indexed.
Not possible?

HA! You're joking right?

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•
 About kirupa.com