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
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.) – greybeard Mar 9 at 6:35