|
Answer» Insertion sort provides several advantages:
a) simple implementation b) efficient for small data sets c) adaptive - efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions d) more efficient in practice than most other simple quadratic, i.e. O(n2) algorithms such as selection sort or bubble sort; the best CASE (nearly sorted input) is O(n) e) stable - does not change the RELATIVE order of elements with equal keys f) in-place - only requires a constant amount O( 1) of additional memory space g) online - can sort a LIST as it receives it Insertion sort provides several advantages: a) simple implementation b) efficient for small data sets c) adaptive - efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions d) more efficient in practice than most other simple quadratic, i.e. O(n2) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n) e) stable - does not change the relative order of elements with equal keys f) in-place - only requires a constant amount O( 1) of additional memory space g) online - can sort a list as it receives it
|