Quick Sort of a Linked List

Quick Sort - Main Idea

1. Select a node (Probably Head node) as Pivot Node
2. Traverse through the remaining nodes to divide into two lists - one containing smaller or equal values and another containing larger values.
3. Recursively apply the sort algorithm to two smaller lists. As a base case, the recursive method will return the input when the input list is of size 1 or 0.
4. Merge First List, Pivot and Second List

Partition

Partition Method selects head node of given list as Pivot node. Based upon this pivot, the input list is divided into two smaller lists - First one with smaller or equal value and Second one with larger values.

Return Type

This method will return an array of Three Nodes - First one is head of first list, Second is Pivot node and the Third is the head of the second list.

Sort Helper

sortHelper() is the recursive method that recursively sorts the smaller lists to finally return the sorted list.

Return Type

This method returns an array of two nodes - Head and Tail nodes of the Sorted List. They are required to ultimately merge the smaller lists and pivot.

Merge

merge() method merges the two smaller sorted list and the pivot.

Return Type

This method returns an array of two nodes - Head and Tail nodes of the Sorted List. They are required to ultimately merge the smaller lists and pivot.

Complete Implementation

---

---

---