Better average behavior
Same worst-case behavior
Worst-case is extremely rare
Algorithms are much simpler