 Bubble sort was analyzed as early as 1956.Comparison sorting algorithms have a fundamental requirement of Ω("n" log "n") comparisons (some input sequences will require a multiple of "n" log "n" comparisons); algorithms not based on comparisons, such as counting sort, can have better performance.Asymptotically optimal algorithms have been known since the mid-20th century—useful new algorithms are still being invented, with the now widely used Timsort dating to 2002, and the library sort being first published in 2006.