Aisuko Li

Aisuko Li

Interested in Quantum computing and MIT-Scheme, Student of RMIT

Sorting algorithm

less than 1 minute read

1.3.3 Comparison sorts

  First algorithm to finish Last algorithm to finish
Random Shell Selection
Nearly sorted Insertion Selection
Reversed Shell Selection
Few unique Quick3 Selection

Comparison sorts

There are so many comparison sorts algorithms,

  • Is it stable or not is the most important metric
  • Average is the second important metric
Name Best Average Worst Memory Stable Method
Block sort n nlogn nlogn 1 Yes Insertion & Merging
Timesort n nlogn nlogn n Yes Insertion & Merging
Cubesort n nlogn nlogn n Yes Insertion
Merge soft nlogn nlogn nlogn n Yes Insertion
Tree soft nlogn nlogn nlogn(balanced) n Yes Insertion

A comparison sort cannot perform better than O(nlogn).

You May Also Enjoy

How to read a paper

1 minute read

Overview It is important for us to read a paper as soon as we can. So, here is a useful strategy.

Foreign Function Interface In Rust

less than 1 minute read

FFI The Foreign Function Interface (FFI) is a feature of many programming languages that allows them to call functions and use data structures defined in ano...