the code now contains snippet to create the linked list too!
any questions can be directed to raghu_tillu@hotmail.com

``````// SampleLinkedListSortTest.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>

{
int data;

int main()
{
int numNodes = 0;
int index = 0;
int *tempArray = NULL;

//numNodes -> no of nodes in the linked list
numNodes = 7;
tempArray = (int *)calloc(numNodes,sizeof(int));
if(!tempArray)
{
printf("\nMemory allocation for dynamic array failed ...\n");
return 0;
}
fflush(stdin);
fflush(stdout);

for(index = 0;index < numNodes;index++)
{
scanf("%d",&tempArray[index]);
}

{
free(tempArray);
return 0;
}
//we don't need the temp array anymore
free(tempArray);

return 0;
}

/* This Function creates the linked list (recursively)*/
{
static int currentLevel = 0;

if(currentLevel >= maxLevel)
{
return NULL;
}
if(!temp)
{
printf("\nMemory allocation for linkedListNode creation failed ..\n");
return NULL;
}
temp->data = tempArray[currentLevel];
currentLevel++;
currentLevel--;

if(currentLevel == 0)
{
}
return temp;
}

/* This function does the MergeSort */
{

{
return;
}
{
return;
}
{
return;
}
//Keep splitting the list in the middle

//head now points to the merged list
}

// This function Merges 2 sorted linked lists into a sorted single list
{
//We need 2 pointers in both the lists to merge the nodes

//Do the Null Pointer Checks
{
return NULL;
}
{
return NULL;
}
{
}
{
}
//Initialize the pointers in left, rite Lists
leftRear = NULL;
riteRear = NULL;

// If there is only one node in both the lists
// then simply do a check and merge the nodes
if(leftFront->next == NULL && riteFront->next == NULL)
{
if(leftFront->data < riteFront->data)
{
leftFront->next = riteFront;
}
else
{
riteFront->next = leftFront;
}
}

//If either of the list has more than 1 node
/*The idea here is to have a riteFront pointer as a checkpoint
and keep moving the leftFront pointer until you reach a node
on the rite list  whose value is > leftFront->data, then merge at that node using
the rear pointers */
while(leftFront != NULL && riteFront != NULL)
{
//keep traversing until you hit a node on the left list
//such that its value is > the value on rite list
while(leftFront != NULL && leftFront->data < riteFront->data)
{
leftRear = leftFront;
leftFront = leftFront->next;
}
// check for NULL pointers
if(leftFront != NULL && riteFront != NULL)
{
/*If the rear pointer is pointing to NULL it indicates
the data on the ritelist to merge is supposed to get
to the beginning of the merged list */
if(leftRear == NULL)
{
riteRear = riteFront;
riteFront = riteFront->next;
leftRear = riteRear;
leftRear->next = leftFront;
if(!riteFront)
{
break;
}
}
//Else the node is supposed to merged in between / end of the merged list
else
{
riteRear = riteFront;
riteFront = riteFront->next;
leftRear->next = riteRear;
leftRear = leftRear->next;
leftRear->next = leftFront;
if(!riteFront)
{
break;
}
}
if(leftFront->data < riteFront->data)
{
leftRear = leftFront;
leftFront = leftFront->next;
}
else
{
continue;
}
}
}// end of while

if(leftFront == NULL && riteFront != NULL)
{
leftRear->next = riteFront;
}
}

/*This function splits the given list into 2 at the middle,
{
{
return;
}
{
return;
}
{
return;
}

if(!(riteTemp->next))
{
return;
}
while(riteTemp->next != NULL)
{
riteTemp = riteTemp->next;
if(riteTemp->next != NULL)
{
leftTemp = leftTemp->next;
riteTemp = riteTemp->next;
}
else
{
leftTemp->next = NULL;
}
}
{
leftTemp->next = NULL;
}
return;
}

/* This function displays the linked list */
{
{
}
}``````
4
Contributors
4
Replies
5
Views
11 Years
Discussion Span
Last Post by virusfree

excellent work. Only two suggestions:
1. fflush(stdin); -- fflush() is guarenteed to only work with output streams. Some compilers allow it for input streams, but that is compiler-specific and will not work on many compilers.

2. In the loop that gets keyboard input you should add a prompt to that the program does not appear to be hung up and doing nothing

``````for(index = 0;index < numNodes;index++)
{
printf("\rEnter item number %d ...", index);
scanf("%d",&tempArray[index]);
}``````

The behaviour of fflush( stdin ) is always undefined whatever be the compiler -- its just that some compilers let you get away with it.

And as far as sorting the linked list is concerned, there is another simple way of doing it -- sort the list as and when the data is entered so that the list is always in sorted form. Before adding each data element, make a search through the entire llist to find where that data exactly belongs to so that it can be inserted at the appropriate position.

Thank you.

to ~s.o.s~

ok, but what if you are given the option of only sorting the list and not creating it?, I wrote CreateLinkedList only as an addon to test it.

Hi,

if you want a fast an easy algorithm for sorting