# QuickSort of linked lists optimised for duplicates

This is an past year question for a school exam that I do not suggested solutions for.

Problem Description

Quick Sort is not stable because of need to swap values in array when partition is done. If we store the values to be sorted in a linked list, we can make quick sort stable. Also, we can easily improve the performance of Quick Sort by grouping all the values that are equal to the pivot to the middle so they do not need to be considered during the subsequent partitions. Consider the following code.

function ListNode quickSort(ListNode head)
partition(params1)
ListNode front = quickSort(params2)
ListNode middle = params3
ListNode back = quickSort(params4)
return combine(front,middle,back)


Task

Identify what should be params1,params2,params3,params4

Use pseudocode to describe the partition method. Make sure that special cases such as when there is a null in parameter is taken care of. Also, the new version of QuickSort is in-place.

I think that quickSort should return the head node of the list, but then middle seems strangely placed in the code as I would think of putting it after after partition. Also, I do not know the pseudocode standards for linked list and whether it is similar to the case of the normal one done with arrays. Can anyone help me with this?

• putting [middle] after after partition I cannot understand that. (It took me a while, anyway, to see that the structure proposed might work with Lomuto partition.) Mar 9, 2019 at 6:35

## 1 Answer

The point is that with linked lists you can reorganize them in-place. So, your partition method should return three separate lists: lower, middle and higher. Each list contains nodes from source list, only pointers are manipulated.