COMP2521
Data Structures & Algorithms
Week 8.5
Sort Summary
1
Sorting Summray
Comparisons Extra storage
required?
Stability Adaptive
Selection N^2 No Possible No
Insertion N^2 No Possible Possible if it stops can when position is found
Bubble N <> N^2 No Possible Possible if it terminates when no swaps
Merge N*log(N) Yes Possible Possible
Quick N*log(N) <> N^2 No Easy for lists, hard
for arrays
Possible
2