About QuickSort

Wikipedia QuickSort definition.

General idea revolves around partitioning a list where values less than pivot go into left list while greater than go into right list.
Pivot here is the first item of the passed in list. We apply this recursively to the sublists them merge left+pivot+right.

CPP Code

First of all not a cpp developer so if you can improve this them post a comment with suggestions.

template 
Node * List::quick_sort_recursive(Node* list)
{
	//Base case : list  is NULL
	if(list ==  NULL){
		return NULL;
	}

	//We choose first entry in the list as the pivot node
	Node * pivotNode = new Node();
	pivotNode->entry=list->entry;
	Record pivot = pivotNode->entry;

	Node *tmp=list->next;
	Node *leftHead=NULL;
	Node *rightHead=NULL;

	Node *leftTail=NULL;
	Node *rightTail=NULL;

	//Partition the list into left/right sublists
	while(tmp != NULL){
		Node *entryNode=new Node();
		entryNode->entry = tmp->entry;
		entryNode->next = NULL;
		if(tmp->entry < pivot){
			if(leftTail == NULL){
				leftTail = entryNode;
				leftHead=entryNode;
			}else{
				leftTail->next=entryNode;
				leftTail=leftTail->next;
			}
		}
		else{
			if(rightTail == NULL){
				rightTail = entryNode;
				rightHead=entryNode;
			}else{
				rightTail->next=entryNode;
				rightTail=rightTail->next;
			}
		}
		tmp = tmp->next;
	}

	//Recursively subdivide the left / right list
	leftHead  = quick_sort_recursive(leftHead);
	rightHead = quick_sort_recursive(rightHead);

	//Combine left+pivot+right
	Node * mergedHead=NULL;
	Node * mergedTail=NULL;

	Node *tmpNode=leftHead;
	while(tmpNode){
		Node *new_node=new Node();
		new_node->entry=tmpNode->entry;
		if(mergedTail == NULL){
			mergedTail = new_node;
			mergedHead= new_node;
		}else{
			mergedTail->next= new_node;
			mergedTail=mergedTail->next;
		}
		tmpNode=tmpNode->next;
	}
	//Pivot point
	if(mergedTail == NULL){
		mergedTail = pivotNode;
		mergedHead = pivotNode;
	}else{
		mergedTail->next=pivotNode;
		mergedTail=mergedTail->next;
	}
	//Right sublist
	tmpNode=rightHead;
	while(tmpNode){
		Node *new_node=new Node();
		new_node->entry=tmpNode->entry;
		mergedTail->next=new_node;
		mergedTail=mergedTail->next;
		tmpNode=tmpNode->next;
	}

	return mergedHead;
}



template 
struct Node {
//  data members
   Node_entry entry;
   Node *next;
//  constructors
   Node();
   Node(Node_entry, Node *link = NULL);
};