# QuickSort on Doubly Linked List

• Difficulty Level : Medium
• Last Updated : 03 Jul, 2022

Following is a typical recursive implementation of QuickSort for arrays. The implementation uses last element as pivot. ## C++

 `/* A typical recursive implementation of Quicksort for array*/`` ` `/* This function takes last element as pivot, places the pivot element at its``   ``correct position in sorted array, and places all smaller (smaller than ``   ``pivot) to left of pivot and all greater elements to right of pivot */``int` `partition (``int` `arr[], ``int` `l, ``int` `h)``{``    ``int` `x = arr[h];``    ``int` `i = (l - 1);`` ` ` ` `    ``for` `(``int` `j = l; j <= h- 1; j++)``    ``{``        ``if` `(arr[j] <= x)``        ``{``            ``i++;``            ``swap (&arr[i], &arr[j]);``        ``}``    ``}``    ``swap (&arr[i + 1], &arr[h]);``    ``return` `(i + 1);``}`` ` `/* A[] --> Array to be sorted, l  --> Starting index, h  --> Ending index */``void` `quickSort(``int` `A[], ``int` `l, ``int` `h)``{``    ``if` `(l < h)``    ``{        ``        ``int` `p = partition(A, l, h); ``/* Partitioning index */``        ``quickSort(A, l, p - 1);  ``        ``quickSort(A, p + 1, h);``    ``}``}`

## Java

 `/* A typical recursive implementation of``   ``Quicksort for array*/``  ` `/* This function takes last element as pivot, ``   ``places the pivot element at its correct ``   ``position in sorted array, and places all ``   ``smaller (smaller than pivot) to left of``   ``pivot and all greater elements to right ``   ``of pivot */``static` `int` `partition (``int` `[]arr, ``int` `l, ``int` `h)``{``    ``int` `x = arr[h];``    ``int` `i = (l - ``1``);``     ` `    ``for``(``int` `j = l; j <= h - ``1``; j++)``    ``{``        ``if` `(arr[j] <= x)``        ``{``            ``i++;``            ``int` `tmp = arr[i];``            ``arr[i] = arr[j];``            ``arr[j] = tmp;``        ``}``    ``}    ``    ``int` `tmp = arr[i + ``1``];``    ``arr[i + ``1``] = arr[h];``    ``arr[h] = tmp;``    ``return``(i + ``1``);``}``  ` `/* A[] --> Array to be sorted,``    ``l  --> Starting index, ``    ``h  --> Ending index */``static` `void` `quickSort(``int` `[]A, ``int` `l, ``                      ``int` `h)``{``    ``if` `(l < h)``    ``{``       ` `        ``// Partitioning index ``        ``int` `p = partition(A, l, h); ``        ``quickSort(A, l, p - ``1``);  ``        ``quickSort(A, p + ``1``, h);``    ``}``}`` ` `// This code is contributed by pratham76.`

## Python3

 `"""A typical recursive implementation of Quicksort for array """``  ` `""" This function takes last element as pivot, ``   ``places the pivot element at its correct ``   ``position in sorted array, and places all ``   ``smaller (smaller than pivot) to left of``   ``pivot and all greater elements to right ``   ``of pivot ``"""`` ` `"""`` ``i --> is the first index in the array`` ``x --> is the last index in the array`` ``tmp --> is a temporary variable for swapping values (integer)``"""``# array arr, integer l, integer h``def`  `partition (arr, l, h):``    ``x ``=` `arr[h]``    ``i ``=` `(l ``-` `1``)``    ``for` `j ``in` `range``(l, h):``        ``if` `(arr[j] <``=` `x):``            ``i ``+``=``1``            ``tmp ``=` `arr[i]``            ``arr[i] ``=` `arr[j]``            ``arr[j] ``=` `tmp`` ` `    ``tmp ``=` `arr[i ``+` `1``]``    ``arr[i ``+` `1``] ``=` `arr[h]``    ``arr[h] ``=` `tmp``    ``return``(i ``+` `1``)`` ` `"""``A --> Array to be sorted,``l --> Starting index, ``h --> Ending index``"""`` ` `# array A, integer l, integer h``def` `quickSort(A, l, h):``    ``if` `(l < h):``        ``p ``=` `partition(A, l, h) ``# pivot index``        ``quickSort(A, l, p ``-` `1``) ``# left``        ``quickSort(A, p ``+` `1``, h) ``# right`` ` `# This code is contributed by humphreykibet.`

## C#

 `/* A typical recursive implementation of``   ``Quicksort for array*/``  ` `/* This function takes last element as pivot, ``   ``places the pivot element at its correct ``   ``position in sorted array, and places all ``   ``smaller (smaller than pivot) to left of``   ``pivot and all greater elements to right ``   ``of pivot */``static` `int` `partition (``int` `[]arr, ``int` `l, ``int` `h)``{``    ``int` `x = arr[h];``    ``int` `i = (l - 1);``     ` `    ``for``(``int` `j = l; j <= h - 1; j++)``    ``{``        ``if` `(arr[j] <= x)``        ``{``            ``i++;``            ``int` `tmp = arr[i];``            ``arr[i] = arr[j];``            ``arr[j] = tmp;``        ``}``    ``}``     ` `    ``int` `tmp = arr[i + 1];``    ``arr[i + 1] = arr[h];``    ``arr[h] = tmp;``    ``return``(i + 1);``}``  ` `/* A[] --> Array to be sorted,``    ``l  --> Starting index, ``    ``h  --> Ending index */``static` `void` `quickSort(``int` `[]A, ``int` `l, ``                      ``int` `h)``{``    ``if` `(l < h)``    ``{        ``        ``// Partitioning index ``        ``int` `p = partition(A, l, h); ``        ``quickSort(A, l, p - 1);  ``        ``quickSort(A, p + 1, h);``    ``}``}`` ` `// This code is contributed by rutvik_56`

## Javascript

 ``

Can we use the same algorithm for Linked List?
Following is C++ implementation for the doubly linked list. The idea is simple, we first find out pointer to the last node. Once we have a pointer to the last node, we can recursively sort the linked list using pointers to first and last nodes of a linked list, similar to the above recursive function where we pass indexes of first and last array elements. The partition function for a linked list is also similar to partition for arrays. Instead of returning index of the pivot element, it returns a pointer to the pivot element. In the following implementation, quickSort() is just a wrapper function, the main recursive function is _quickSort() which is similar to quickSort() for array implementation. Implementation:

## C++

 `// A C++ program to sort a linked list using Quicksort ``#include ``using` `namespace` `std;`` ` `/* a node of the doubly linked list */``class` `Node ``{ ``    ``public``:``    ``int` `data; ``    ``Node *next; ``    ``Node *prev; ``}; `` ` `/* A utility function to swap two elements */``void` `swap ( ``int``* a, ``int``* b ) ``{ ``int` `t = *a; *a = *b; *b = t; } `` ` `// A utility function to find``// last node of linked list ``Node *lastNode(Node *root) ``{ ``    ``while` `(root && root->next) ``        ``root = root->next; ``    ``return` `root; ``} `` ` `/* Considers last element as pivot, ``places the pivot element at its ``correct position in sorted array, ``and places all smaller (smaller than ``pivot) to left of pivot and all greater``elements to right of pivot */``Node* partition(Node *l, Node *h) ``{ ``    ``// set pivot as h element ``    ``int` `x = h->data; `` ` `    ``// similar to i = l-1 for array implementation ``    ``Node *i = l->prev; `` ` `    ``// Similar to "for (int j = l; j <= h- 1; j++)" ``    ``for` `(Node *j = l; j != h; j = j->next) ``    ``{ ``        ``if` `(j->data <= x) ``        ``{ ``            ``// Similar to i++ for array ``            ``i = (i == NULL)? l : i->next; `` ` `            ``swap(&(i->data), &(j->data)); ``        ``} ``    ``} ``    ``i = (i == NULL)? l : i->next; ``// Similar to i++ ``    ``swap(&(i->data), &(h->data)); ``    ``return` `i; ``} `` ` `/* A recursive implementation ``of quicksort for linked list */``void` `_quickSort(Node* l, Node *h) ``{ ``    ``if` `(h != NULL && l != h && l != h->next) ``    ``{ ``        ``Node *p = partition(l, h); ``        ``_quickSort(l, p->prev); ``        ``_quickSort(p->next, h); ``    ``} ``} `` ` `// The main function to sort a linked list.``// It mainly calls _quickSort() ``void` `quickSort(Node *head) ``{ ``    ``// Find last node ``    ``Node *h = lastNode(head); `` ` `    ``// Call the recursive QuickSort ``    ``_quickSort(head, h); ``} `` ` `// A utility function to print contents of arr ``void` `printList(Node *head) ``{ ``    ``while` `(head) ``    ``{ ``        ``cout << head->data << ``" "``; ``        ``head = head->next; ``    ``} ``    ``cout << endl; ``} `` ` `/* Function to insert a node at the ``beginning of the Doubly Linked List */``void` `push(Node** head_ref, ``int` `new_data) ``{ ``    ``Node* new_node = ``new` `Node; ``/* allocate node */``    ``new_node->data = new_data; `` ` `    ``/* since we are adding at the``    ``beginning, prev is always NULL */``    ``new_node->prev = NULL; `` ` `    ``/* link the old list off the new node */``    ``new_node->next = (*head_ref); `` ` `    ``/* change prev of head node to new node */``    ``if` `((*head_ref) != NULL) (*head_ref)->prev = new_node ; `` ` `    ``/* move the head to point to the new node */``    ``(*head_ref) = new_node; ``} `` ` `/* Driver code */``int` `main() ``{ ``    ``Node *a = NULL; ``    ``push(&a, 5); ``    ``push(&a, 20); ``    ``push(&a, 4); ``    ``push(&a, 3); ``    ``push(&a, 30); `` ` `    ``cout << ``"Linked List before sorting \n"``; ``    ``printList(a); `` ` `    ``quickSort(a); `` ` `    ``cout << ``"Linked List after sorting \n"``; ``    ``printList(a); `` ` `    ``return` `0; ``} `` ` `// This code is contributed by rathbhupendra`

## C

 `// C program to sort a linked list using Quicksort``#include ``#include `` ` `/* a node of the doubly linked list */``struct` `Node``{``    ``int` `data;``    ``struct` `Node *next;``    ``struct` `Node *prev;``};`` ` `/* A utility function to swap two elements */``void` `swap ( ``int``* a, ``int``* b )``{ ``int` `t = *a; *a = *b; *b = t; }`` ` `// A utility function to find last node of linked list``struct` `Node *lastNode(``struct` `Node *root)``{``    ``while` `(root && root->next)``        ``root = root->next;``    ``return` `root;``}`` ` `/* Considers last element as pivot, places the ``pivot element at its correct position in sorted array, ``and places all smaller (smaller than pivot) to left``of pivot and all greater elements to right of pivot */``struct` `Node* partition(``struct` `Node *l, ``struct` `Node *h)``{``    ``// set pivot as h element``    ``int` `x = h->data;`` ` `    ``// similar to i = l-1 for array implementation``    ``struct` `Node *i = l->prev;`` ` `    ``// Similar to "for (int j = l; j <= h- 1; j++)"``    ``for` `(``struct` `Node *j = l; j != h; j = j->next)``    ``{``        ``if` `(j->data <= x)``        ``{``            ``// Similar to i++ for array``            ``i = (i == NULL) ? l : i->next;`` ` `            ``swap(&(i->data), &(j->data));``        ``}``    ``}``    ``i = (i == NULL) ? l : i->next; ``// Similar to i++``    ``swap(&(i->data), &(h->data));``    ``return` `i;``}`` ` `/* A recursive implementation of quicksort for linked list */``void` `_quickSort(``struct` `Node* l, ``struct` `Node *h)``{``    ``if` `(h != NULL && l != h && l != h->next)``    ``{``        ``struct` `Node *p = partition(l, h);``        ``_quickSort(l, p->prev);``        ``_quickSort(p->next, h);``    ``}``}`` ` `// The main function to sort a linked list.``// It mainly calls _quickSort()``void` `quickSort(``struct` `Node *head)``{``    ``// Find last node``    ``struct` `Node *h = lastNode(head);`` ` `    ``// Call the recursive QuickSort``    ``_quickSort(head, h);``}`` ` `// A utility function to print contents of arr``void` `printList(``struct` `Node *head)``{``    ``while` `(head)``    ``{``        ``printf``(``"%d "``, head->data);``        ``head = head->next;``    ``}``    ``printf``(``"\n"``);``}`` ` `/* Function to insert a node at the ``beginning of the Doubly Linked List */``void` `push(``struct` `Node** head_ref, ``int` `new_data)``{``    ``struct` `Node* new_node = (``struct` `Node*) ``               ``malloc``(``sizeof``(``struct` `Node)); ``/* allocate node */``    ``new_node->data = new_data;`` ` `    ``/* since we are adding at the beginning,``    ``prev is always NULL */``    ``new_node->prev = NULL;`` ` `    ``/* link the old list off the new node */``    ``new_node->next = (*head_ref);`` ` `    ``/* change prev of head node to new node */``    ``if` `((*head_ref) != NULL) (*head_ref)->prev = new_node ;`` ` `    ``/* move the head to point to the new node */``    ``(*head_ref) = new_node;``}`` ` `// Driver Code``int` `main(``int` `argc, ``char` `**argv)``{``    ``struct` `Node *a = NULL;``    ``push(&a, 5);``    ``push(&a, 20);``    ``push(&a, 4);``    ``push(&a, 3);``    ``push(&a, 30);`` ` `    ``printf``(``"Linked List before sorting \n"``);``    ``printList(a);`` ` `    ``quickSort(a);`` ` `    ``printf``(``"Linked List after sorting \n"``);``    ``printList(a);`` ` `    ``return` `0;``}`

## Java

 `// A Java program to sort a linked list using Quicksort``class` `QuickSort_using_Doubly_LinkedList{``    ``Node head;``   ` `/* a node of the doubly linked list */`  `    ``static` `class` `Node{``        ``private` `int` `data;``        ``private` `Node next;``        ``private` `Node prev;``         ` `        ``Node(``int` `d){``            ``data = d;``            ``next = ``null``;``            ``prev = ``null``;``        ``}``    ``}``     ` `// A utility function to find last node of linked list    ``    ``Node lastNode(Node node){``        ``while``(node.next!=``null``)``            ``node = node.next;``        ``return` `node;``    ``}``     ` ` ` `/* Considers last element as pivot, places the pivot element at its``   ``correct position in sorted array, and places all smaller (smaller than``   ``pivot) to left of pivot and all greater elements to right of pivot */``    ``Node partition(Node l,Node h)``    ``{``       ``// set pivot as h element``        ``int` `x = h.data;``         ` `        ``// similar to i = l-1 for array implementation``        ``Node i = l.prev;``         ` `        ``// Similar to "for (int j = l; j <= h- 1; j++)"``        ``for``(Node j=l; j!=h; j=j.next)``        ``{``            ``if``(j.data <= x)``            ``{``                ``// Similar to i++ for array``                ``i = (i==``null``) ? l : i.next;``                ``int` `temp = i.data;``                ``i.data = j.data;``                ``j.data = temp;``            ``}``        ``}``        ``i = (i==``null``) ? l : i.next;  ``// Similar to i++``        ``int` `temp = i.data;``        ``i.data = h.data;``        ``h.data = temp;``        ``return` `i;``    ``}``     ` `    ``/* A recursive implementation of quicksort for linked list */``    ``void` `_quickSort(Node l,Node h)``    ``{``        ``if``(h!=``null` `&& l!=h && l!=h.next){``            ``Node temp = partition(l,h);``            ``_quickSort(l,temp.prev);``            ``_quickSort(temp.next,h);``        ``}``    ``}``     ` `    ``// The main function to sort a linked list. It mainly calls _quickSort()``    ``public` `void` `quickSort(Node node)``    ``{``        ``// Find last node``        ``Node head = lastNode(node);``         ` `        ``// Call the recursive QuickSort``        ``_quickSort(node,head);``    ``}``     ` `     ``// A utility function to print contents of arr``     ``public` `void` `printList(Node head)``     ``{``        ``while``(head!=``null``){``            ``System.out.print(head.data+``" "``);``            ``head = head.next;``        ``}``    ``}``     ` `    ``/* Function to insert a node at the beginning of the Doubly Linked List */``    ``void` `push(``int` `new_Data)``    ``{``        ``Node new_Node = ``new` `Node(new_Data);     ``/* allocate node */``         ` `        ``// if head is null, head = new_Node``        ``if``(head==``null``){``            ``head = new_Node;``            ``return``;``        ``}``         ` `        ``/* link the old list off the new node */``        ``new_Node.next = head;``         ` `        ``/* change prev of head node to new node */``        ``head.prev = new_Node;``         ` `        ``/* since we are adding at the beginning, prev is always NULL */``        ``new_Node.prev = ``null``;``         ` `        ``/* move the head to point to the new node */``        ``head = new_Node;``    ``}``     ` `    ``/* Driver program to test above function */``    ``public` `static` `void` `main(String[] args){``            ``QuickSort_using_Doubly_LinkedList list = ``new` `QuickSort_using_Doubly_LinkedList();``             ` `             ` `            ``list.push(``5``);``            ``list.push(``20``);``            ``list.push(``4``);``            ``list.push(``3``);``            ``list.push(``30``);``           ` `             ` `            ``System.out.println(``"Linked List before sorting "``);``            ``list.printList(list.head);``            ``System.out.println(``"\nLinked List after sorting"``);``            ``list.quickSort(list.head);``            ``list.printList(list.head);``         ` `    ``}``}`` ` `// This code has been contributed by Amit Khandelwal`

## Python3

 `# A Python program to sort a linked list using Quicksort``head ``=` `None`` ` `# a node of the doubly linked list``class` `Node:``    ``def` `__init__(``self``, d):``        ``self``.data ``=` `d``        ``self``.``next` `=` `None``        ``self``.prev ``=` `None`` ` `# A utility function to find last node of linked list``def` `lastNode(node):``    ``while``(node.``next` `!``=` `None``):``            ``node ``=` `node.``next``;``    ``return` `node;`` ` `# Considers last element as pivot, places the pivot element at its``#   correct position in sorted array, and places all smaller (smaller than``#   pivot) to left of pivot and all greater elements to right of pivot ``def` `partition(l, h):`` ` `    ``# set pivot as h element``        ``x ``=` `h.data;``          ` `        ``# similar to i = l-1 for array implementation``        ``i ``=` `l.prev;``         ` `        ``j ``=` `l``         ` `        ``# Similar to "for (int j = l; j <= h- 1; j++)"``        ``while``(j !``=` `h):``            ``if``(j.data <``=` `x):``               ` `                ``# Similar to i++ for array``                ``i ``=` `l ``if``(i ``=``=` `None``) ``else` `i.``next``;`` ` `                ``temp ``=` `i.data;``                ``i.data ``=` `j.data;``                ``j.data ``=` `temp;``            ``j ``=` `j.``next``                         ` `        ``i ``=` `l ``if` `(i ``=``=` `None``) ``else` `i.``next``;  ``# Similar to i++``        ``temp ``=` `i.data;``        ``i.data ``=` `h.data;``        ``h.data ``=` `temp;``        ``return` `i;`` ` `# A recursive implementation of quicksort for linked list ``def` `_quickSort(l,h):``    ``if``(h !``=` `None` `and` `l !``=` `h ``and` `l !``=` `h.``next``):``            ``temp ``=` `partition(l, h);``            ``_quickSort(l,temp.prev);``            ``_quickSort(temp.``next``, h);``         ` `# The main function to sort a linked list. It mainly calls _quickSort()``def` `quickSort(node):``   ` `    ``# Find last node``        ``head ``=` `lastNode(node);``          ` `        ``# Call the recursive QuickSort``        ``_quickSort(node,head);`` ` `# A utility function to print contents of arr``def` `printList(head):``    ``while``(head !``=` `None``):``            ``print``(head.data, end``=``" "``);``            ``head ``=` `head.``next``;``         ` `# Function to insert a node at the beginning of the Doubly Linked List ``def` `push(new_Data):``    ``global` `head;``    ``new_Node ``=` `Node(new_Data);     ``# allocate node ``          ` `    ``# if head is null, head = new_Node``    ``if``(head ``=``=` `None``):``        ``head ``=` `new_Node;``        ``return``;``     ` `    ``# link the old list off the new node ``    ``new_Node.``next` `=` `head;``         ` `    ``# change prev of head node to new node ``    ``head.prev ``=` `new_Node;``         ` `    ``# since we are adding at the beginning, prev is always NULL ``    ``new_Node.prev ``=` `None``;``         ` `    ``# move the head to point to the new node ``    ``head ``=` `new_Node;`` ` `# Driver program to test above function ``push(``5``);``push(``20``);``push(``4``);``push(``3``);``push(``30``);`` ` ` ` `print``(``"Linked List before sorting "``);``printList(head);``print``(``"\nLinked List after sorting"``);``quickSort(head);``printList(head);`` ` `# This code is contributed by _saurabh_jaiswal`

## C#

 `// A C# program to sort a linked list using Quicksort`` ` `using` `System;``    ``/* a node of the doubly linked list */``    ``public` `class` `Node``    ``{``        ``public` `int` `Data;``        ``public` `Node Next;``        ``public` `Node Prev;`` ` `        ``public` `Node(``int` `d)``        ``{``            ``Data = d;``              ``/* Prev and Next are left Null */``        ``}``    ``}`` ` `    ``public` `class` `DoublyLinkedList``    ``{``        ``private` `Node _head;``        ``public` `Node Head``        ``{``            ``get` `=> _head;``            ``set` `=> _head = value;``        ``}`` ` `        ``// A utility function to find the last node of linked list``        ``private` `Node LastNode(Node node)``        ``{``            ``while` `(node.Next != ``null``)``                ``node = node.Next;``            ``return` `node;``        ``}`` ` `        ``/* Considers last element as pivot,``        ``places the pivot element at its``        ``correct position in a sorted array,``        ``and places all smaller (smaller than``        ``pivot) to left of pivot and all``        ``greater elements to right of pivot */``        ``private` `Node Partition(Node last, Node head)``        ``{``            ``// set pivot as h element``            ``int` `pivot = head.Data;`` ` `            ``// similar to i = l-1 for array implementation``            ``Node i = last.Prev;``            ``int` `temp;`` ` `            ``// Similar to "for (int j = l; j <= h- 1; j++)"``            ``for` `(Node j = last; j != head; j = j.Next)``            ``{``                ``if` `(j.Data <= pivot)``                ``{``                    ``// Similar to i++ for array``                    ``i = (i == ``null``) ? last : i.Next;``                    ``temp = i.Data;``                    ``i.Data = j.Data;``                    ``j.Data = temp;``                ``}``            ``}``            ``i = (i == ``null``) ? last : i.Next; ``// Similar to i++``            ``temp = i.Data;``            ``i.Data = head.Data;``            ``head.Data = temp;``            ``return` `i;``        ``}`` ` `        ``/* A recursive implementation of``        ``quicksort for linked list */``        ``private` `void` `RecursiveQuickSort(Node last, Node head)``        ``{``            ``if` `(head != ``null` `&& last != head && last != head.Next)``            ``{``                ``Node temp = Partition(last, head);``                ``RecursiveQuickSort(last, temp.Prev);``                ``RecursiveQuickSort(temp.Next, head);``            ``}``        ``}`` ` `        ``// The main function to sort a linked list.``        ``// It mainly calls _quickSort()``        ``public` `void` `QuickSort(Node node)``        ``{``            ``// Find last node``            ``Node head = LastNode(node);`` ` `            ``// Call the recursive QuickSort``            ``RecursiveQuickSort(node, head);``        ``}`` ` `        ``// A utility function to print contents of arr``        ``public` `void` `PrintList(Node head)``        ``{``            ``while` `(head != ``null``)``            ``{``                ``Console.Write(head.Data + ``" "``);``                ``head = head.Next;``            ``}``        ``}`` ` `        ``/* Function to insert a node at the``        ``beginning of the Doubly Linked List */``        ``public` `void` `Push(``int` `new_Data)``        ``{``            ``Node new_Node = ``new` `Node(new_Data); ``/* allocate node */`` ` `            ``// if head is null, head = new_Node``            ``if` `(_head == ``null``)``            ``{``                ``_head = new_Node;``                ``return``;``            ``}`` ` `            ``/* link the old list off the new node */``            ``new_Node.Next = _head;`` ` `            ``/* change prev of head node to new node */``            ``_head.Prev = new_Node;`` ` `            ``/* since we are adding at the``            ``beginning, prev is always NULL */`` ` `            ``/* move the head to point to the new node */``            ``_head = new_Node;``        ``}`` ` `        ``/* Driver code */``    ``}``    ``public` `class` `QuickSort_using_Doubly_LinkedList``    ``{``        ``public` `static` `void` `Main(String[] args)``        ``{``            ``var` `list = ``new` `DoublyLinkedList();`` ` `            ``list.Push(5);``            ``list.Push(20);``            ``list.Push(4);``            ``list.Push(3);``            ``list.Push(30);`` ` `            ``Console.WriteLine(``"Linked List before sorting "``);``            ``list.PrintList(list.Head);``            ``Console.WriteLine(``"\nLinked List after sorting"``);``            ``list.QuickSort(list.Head);``            ``list.PrintList(list.Head);``        ``}``    ``}`

## Javascript

 ``

Output

```Linked List before sorting
30 3 4 20 5
Linked List after sorting
3 4 5 20 30 ```

Time Complexity: Time complexity of the above implementation is same as time complexity of QuickSort() for arrays. It takes O(n^2) time in the worst case and O(nLogn) in average and best cases. The worst case occurs when the linked list is already sorted.
Can we implement random quicksort for a linked list?
Quicksort can be implemented for Linked List only when we can pick a fixed point as the pivot (like the last element in the above implementation). Random QuickSort cannot be efficiently implemented for Linked Lists by picking random pivot.

Auxiliary Space: O(n)

The extra space is due to the function call stack.

Exercise:
The above implementation is for a doubly linked list. Modify it for a singly linked list. Note that we don’t have prev pointer in a singly linked list.
Refer QuickSort on Singly Linked List for solution.

My Personal Notes arrow_drop_up