# How do I make a stable sorting algorithm that uses an unstable algorithm as a subroutine

The stable algorithm has to run in O(n) time and must call the following unstable algorithm at least once.

EDIT: Calling unstablesort() is free (costs 0 operations).

def unstablesort(l):
return selectionsort(shuffled(l)) # shuffled(l) returns list l randomized


This is apparently an easy question but frankly I don't know where to start.

• Please reproduce the problem statement as in your homework. An O(n) general sort is not possible.
– user16034
Commented Apr 18, 2023 at 6:20
• Question 1: In which situation does it not matter that the unstable sort is unstable? Question 2: How can you create this situation? Commented Apr 18, 2023 at 13:46
• @gnasher729 When there are no duplicates, I can create that by looping through the list and creating a set but then I don't see how to go about adding the duplicates back in and keeping it O(n). For example if all the items are equal Commented Apr 18, 2023 at 22:08