# #28: QUOBOSORT

Tagged as challenge

Written on 2018-01-30

You happen upon the following note, which seems to describe a novel algorithm for sorting.

QUOBOSORT: a sort made by ROBERT SMITH aka STYLEWARNING

Patents Pending.

SUMMARY
-------

Permute X until the minimum is in the first position of X. When this
occurs, QUOBOSORT the rest of X until we reach an empty listte.

ALGORITHM
---------

QUOBOSORT(X) :=
-- INPUT: a list of integers X
-- OUTPUT: sorted X in ascending order

Q0. Is X an empty list?
Yes: Return X.
No : Go to Q1.
Q1. Find the minimum M of X.
Q2. Randomly permute X.
Q3. Is M in the first position of X?
Yes: Concatenate M and QUOBOSORT(REST(X))
No : Go to Q2.

Implement this algorithm.

Extra Credit: Analyse the time and memory complexity of this algorithm.