Quick sort using linked list

We have already seen in-detail about the quick sort algorithm and its iterative as well as recursive implementation on arrays. In this example we will see how we can use quick sort on linked list.

Example

Input:
30 -> 3 -> 4 -> 20 -> 5 -> null 

Output:
3 -> 4 -> 5 -> 20 -> 30 -> null

Quick sort using linked list

The most challenging aspect in soring a linked list is working with pointers to swap the elements position.

Partition

We consider last element as a pivot while partitioning. We traverse through the current list and if a node has value greater than pivot, we move it after tail. If the node has smaller value, we keep it at its current position.

const partitionLast = (start, end) => {
  //Base case
  if(start === end || start === null || end === null){
    return start;
  }
  
  let pivot_prev = start;
  let curr = start;
  let pivot = end.element;
  
  // iterate till one before the end,  
  // no need to iterate till the end  
  // because end is pivot 
  while(start !== end){
    if(start.element < pivot){
      // keep tracks of last modified item 
      pivot_prev = curr;
      let temp = curr.element;
      curr.element = start.element;
      start.element = temp;
      curr = curr.next;
    }
    
    start = start.next;
  }
  
  // swap the position of curr i.e. 
  // next suitable index and pivot 
  let temp = curr.element;
  curr.element = pivot;
  end.element = temp;
  
  // return one previous to current 
  // because current is now pointing to pivot 
  return pivot_prev;
}

Performing sort

We first call the partition function which places the pivot at its correct position and returns pivot. Once the pivot is placed at its position, we find the tail node of left side (list before the pivot) and recur for left list and then recur for the right list.

const sort = (start, end) => {
  if(start === end){
    return;
  }
  
  // split list and partion recurse 
  let pivot_prev = partitionLast(start, end);
  sort(start, pivot_prev);
  
  // if pivot is picked and moved to the start, 
  // that means start and pivot is same  
  // so pick from next of pivot 
  if(pivot_prev !== null && pivot_prev === start){
    sort(pivot_prev.next, end);
  }
  // if pivot is in between of the list, 
  // start from next of pivot,  
  // since we have pivot_prev, so we move two nodes 
  else if(pivot_prev !== null && pivot_prev.next !== null){ 
    sort(pivot_prev.next.next, end);
  }
}

Input:
let list = new linkedlist(); 
list.append(30); 
list.append(3); 
list.append(4); 
list.append(20); 
list.append(5); 

//Move to the end (tail node)  
let end = list.getHead(); 
while(end.next != null){ 
   end = end.next; 
}

//Get the start
let start = list.getHead();

//Sort the list
sort(start , end);

//Print the sorted list 
while(start){
  console.log(start.element);
  start = start.next;
}

Output:
3
4
5
20
30

Time complexity: O(nlogn).
Space complexity: O(logn).