Merge sort using linked lists

[tonykjose]

I have got a small problem with this program. It takes a user's input of numbers
and sorts them by merge sort in increasing order using linked lists.
Unfortunately, a segmentation fault appears immediately after I input the numbers. Probably something to do with the merge sort function.
Help!

#include<iostream>
#include<limits>
using namespace std;
int psize,qsize,k,i;
struct node
	{
		int info;
		node *next;
	}*p,*q,*front,*front1,*rear1,*rear,*newptr,*ptr,*np,*np1;
node *create_new_node(int);
void insert (node *);
void insert1 (node *);
void display(node *);
void MergeSort(node *,int);
void copy(node *,node *);

int main()
	{
		int length=0;
		front=rear=NULL;
		int inf;
		char ch='y';
		inf=INT_MIN;
		newptr=create_new_node(inf); //assigning least integer value to first node
		if(newptr==NULL)
			{
				cout<<"\nCannot create new node..";
				return 0;
			}
		insert(newptr); //calling fuction to insert new node to the linked list
		while(ch=='y'||ch=='Y')
			{
				cout<<"\nEnter information for the new node..";
				cin>>inf;
				newptr=create_new_node(inf);
				if(newptr==NULL) //checking if new node creation is successful
					{
						cout<<"\nCannot create new node..";
						return 0;
					}
  				insert(newptr);
  				length++;
  				cout<<"\nNow the list is:\n";
  				display(front);
  				cout<<"\nPress Y to enter more nodes, N to exit..";
  				cin>>ch;
			}
  		MergeSort(front,length);
  	}

void MergeSort(node *np,int len)
	{
		p = np ;
		q = np ;

		int k = 1;
		for ( i=0;i<k;i++)
			{
				q = q->next;
			}
		qsize = 0;
		psize=0 ;
		int counter = 0 ;
		while(k<=len/2)
			{
				while (counter<len)
					{
						while((psize<k)&&(qsize<k))
							{
								if((q==NULL)&&(p==NULL))
								break;

								if((q->info)<(p->info))
									{
										newptr = create_new_node(q->info);
										insert1(newptr);
										q = q->next;
										qsize++;
										counter++;
									}
								else
									{
  										newptr = create_new_node(p->info);
  										insert1(newptr);
  										p = p->next;
  										psize++;
  										counter++;
									}
							}
						p = q;
						for ( i=0;i<k;i++)
							{
								q = q->next;
							}
					}
				k=2*k;
				copy(front1,front);
				counter = 0;
				qsize = 0;
				psize=0 ;
			}
		display(front1);
	}

node *create_new_node(int n)  //fuction to create new node
	{
		ptr=new node;
		ptr->info=n;
		ptr->next=NULL;
		return ptr;
	}

void copy(node *np,node *np1)
	{
  		while(np!=NULL)
			{
				np1 = np;
				np=np->next;
			}
	}
void insert(node *np) //function to insert new node to linked list
	{
		if((front==NULL)&&(rear==NULL))
			{
  				front=np;
  				rear=np;
			}
		else
			{
  				rear->next=np;
				rear = np;
			}

	}

void insert1(node *np)
	{
		if((front1==NULL)&&(rear1==NULL))
			{
  				front1=np;
  				rear1=np;
			}
		else
			{
  				rear1->next=np;
			}

	}

void display(node *np) //function to display the list
	{
		while(np!=NULL)
			{
  				cout<<np->info<<"->";
 				 np=np->next;
			}
		cout<<"!!!";
	}

[StuXYZ]

There are many many things wrong with this.

Let us start with MergeSort.

Ok explain

int k = 1;
  for ( i=0;i<k;i++)
  {
    q = q->next;
  }

Ok we have (A) a global variable as a loop index !!
(B) a loop that never does anything more than

q = np->next;

Then we have three (!!) while loops

Then we have a piece of repeated code in the if(q->info < p->info) if/else construct. Likely to cause errors later.

The we have a while loop with a first line break / So what about making it part of the condition OR was the intention to escape higher.

Then you break out of the while loop on the condition that q IS null
and then expect p=q and q=p->next to work.

Overall, this is a mess. Sorry, I think you compeletely miss understood merge sort. The normal structure is something like three whiles but not embedded. Try http://en.wikipedia.org/wiki/Merge_sort
to see how.

[rcgldr]

Note that the wikipedia now includes example pseudo code for a bottom up merge sort for linked list.

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