What is the below sorting algorithm?
start with list I of n items
choose pivot item v from I.
partition I into 2 unsorted lists I1 & I2.
- I1 : all keys smaller than V's key
- I1 : all keys larger than V's key
- items with same key as v can go into either list
- the pivot v does not go into either list.
sort I1 recursively , yielding sorted list S1.
sort I2 recursively , yielding sorted list S2.
Concatenate S1, v, & S2, yielding sorted list S.