Skip to main content

Perform quick sort in doubly linked list

This article addresses the implementation of the QuickSort algorithm on a doubly linked list. QuickSort is a popular sorting algorithm known for its efficiency and ease of implementation. This article will guide you through the process of performing QuickSort on a doubly linked list, along with explanations and code examples.

Problem Statement

Given a doubly linked list, the goal is to sort its elements in non-decreasing order using the QuickSort algorithm.


Consider the following doubly linked list:

4 <-> 3 <-> 7 <-> 1 <-> -1 <-> 6 <-> 2 <-> 8 <-> -2 <-> 0

After applying QuickSort, the list should become:

-2 <-> -1 <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 6 <-> 7 <-> 8

Idea to Solve

QuickSort is a recursive sorting algorithm that works by selecting a pivot element and partitioning the array into two sub-arrays – elements less than the pivot and elements greater than the pivot. This process is repeated for the sub-arrays until the entire list is sorted.


function partition(first, last):
    current = first
    location = first.prev
    temp = 0
    while current is not null and current is not last:
        if <=
            if location is null:
                location = first
                move location to the next node
            swap and
        move current to the next node
    if location is null:
        location = first
        move location to the next node
    swap and
    return location

function quickSort(first, last):
    if first is not last and first is not null and 
       last is not null and is not first:
        node = partition(first, last)
        if node is not null:
            quickSort(, last)
            quickSort(first, node.prev)

Algorithm Explanation

  1. Implement a partition function that takes two pointers, first and last, as parameters.
  2. Initialize current to first and location to first.prev.
  3. Traverse the linked list with the current pointer and swap nodes' data if necessary, keeping track of the location of the pivot.
  4. After traversing, swap the data of the last node and the location node.
  5. Return the location node as the new pivot.
  6. Implement the quickSort function that recursively sorts the linked list:
    • If the base conditions are met (i.e., valid pointers and non-empty sub-array), partition the list using the partition function and obtain the pivot node.
    • Recursively apply quickSort to the sub-arrays before and after the pivot node.

Program List

Time Complexity

The time complexity of QuickSort largely depends on the choice of the pivot. On average, the time complexity is O(n log n), which makes it one of the fastest sorting algorithms.


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment