# 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)


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.) Commented Mar 9, 2019 at 6:35
• Grouping the values equal to the pivot is certainly counterproductive. Because even if there are many equal keys, the pivot may still be different. But you will pay the overhead of handling three lists instead of two anyway (two comparisons per element instead of one). Unless the input is very special, my bet is a degradation of the performance.
– user16034
Commented Jul 18, 2023 at 7:29