Page 4 - Lesson Note-Python Modules and Sorting

Advantage:
1. It is the simplest sorting approach.
2. Best case complexity is of O(N) [for optimized approach] while the array is sorted.
3. Using optimized approach, it can detect already sorted array in first pass with time
complexity of O(1).
4. Stable sort: does not change the relative order of elements with equal keys.
5. In-Place sort.
Disadvantage:
1. Bubble sort is comparatively slower algorithm.

Insertion Sort

Advantage:
1. It can be easily computed.
2. Best case complexity is of O(N) while the array is already sorted.
3. Number of swaps reduced than bubble sort.
4. For smaller values of N, insertion sort performs efficiently like other quadratic sorting
algorithms.
5. Stable sort.
6. Adaptive: total number of steps is reduced for partially sorted array.
7. In-Place sort.
Disadvantage:
1. It is generally used when the value of N is small. For larger values of N, it is inefficient.