## A - compare

- Build a new list as the result
- Transfer the minimum value in original list into new list
- Repeat step 2
- End when the original list has length of 0 or 1

example code:

1 | def sort1(iList): |

## B - recursion

- If the list has a length of 0 or 1, just return it.
- Otherwise, return the minimum value as a single-value list plus the output list of the remnant list.

example code:

1 | def sort2(list): |

## Benchmark

Which one is the best?

Firstly I made 20 640-length-integer list to test two sorting methods.

1 | import random |

Then I copy the result data into R and visualize it:

1 | library(tidyr) |

## The reason

In sort1, we have two loops.

- One is
`for i in range(len(iList))`

and the other is`for x in iList[1:]`

which is inside the first one. - For an i-th iteration, it has a sub-loop with
`n-i`

iteration (`n=len(list)`

). - So each sorting has $\frac{1}{2}n^2+n+\frac{1}{2}$ times iterations.
- Sort1’ order of growth is $O(n^2)$.

- One is
In sort2, however, we use recursive loop.

- For the last recursion, it only have 2-time calculation. One for checking if’s condition and one for return value.
- The second last one has 4-time calculation plus 2-time calculation from the last recursion.
- The third last one also has 4-time calculation plus 6-time calculation from the second last recursion.
- Overall, recursive method has $4*(n-1)+2=4n-2$ times of calculation.
- Its order of growth is $O(n)$.

In conclusion, their calculation amount is not the same and this is the reason that sort1 spend much more time.

The advantage of recursion can be more obvious in big data.