Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

 2 added 10 characters in body edited Dec 2 '13 at 19:04 Patrick87 11.9k11 gold badge3535 silver badges7272 bronze badges In general terms, there are the $$O(n^2)$$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances; Quicksort, which is worst-case $$O(n^2)$$ but quite often $$O(n\log n)$$ with good constants and properties and which can be used as a general-purpose sorting procedure; the $$O(n\log n)$$ algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms; and the $$O(n)$$, or linear, sorting algorithms for lists of integers, such as radix, bucket and counting sorts, which may be suitable depending on the nature of the integers in your lists. If the elements in your list are such that all you know about them is the total order relationship between them, then optimal sorting algorithms will have complexity $$O(n\log n)$$$$\Omega(n\log n)$$. This is a fairly cool result and one for which you should be able to easily find details online. The linear sorting algorithms exploit further information about the structure of elements to be sorted, rather than just the total order relationship among elements. Even more generally, optimality of a sorting algorithm depends intimately upon the assumptions you can make about the kind of lists you're going to be sorting (as well as the machine model on which the algorithm will run, which can make even otherwise poor sorting algorithms the best choice; consider bubble sort on machines with a tape for storage). The stronger your assumptions, the more corners your algorithm can cut. Under very weak assumptions about how efficiently you can determine "sortedness" of a list, the optimal worst-case complexity can even be $$O(n!)$$$$\Omega(n!)$$. This answer deals only with complexities. Actual running times of implementations of algorithms will depend on a large number of factors which are hard to account for in a single answer. In general terms, there are the $$O(n^2)$$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances; Quicksort, which is worst-case $$O(n^2)$$ but quite often $$O(n\log n)$$ with good constants and properties and which can be used as a general-purpose sorting procedure; the $$O(n\log n)$$ algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms; and the $$O(n)$$, or linear, sorting algorithms for lists of integers, such as radix, bucket and counting sorts, which may be suitable depending on the nature of the integers in your lists. If the elements in your list are such that all you know about them is the total order relationship between them, then optimal sorting algorithms will have complexity $$O(n\log n)$$. This is a fairly cool result and one for which you should be able to easily find details online. The linear sorting algorithms exploit further information about the structure of elements to be sorted, rather than just the total order relationship among elements. Even more generally, optimality of a sorting algorithm depends intimately upon the assumptions you can make about the kind of lists you're going to be sorting (as well as the machine model on which the algorithm will run, which can make even otherwise poor sorting algorithms the best choice; consider bubble sort on machines with a tape for storage). The stronger your assumptions, the more corners your algorithm can cut. Under very weak assumptions about how efficiently you can determine "sortedness" of a list, the optimal worst-case complexity can even be $$O(n!)$$. This answer deals only with complexities. Actual running times of implementations of algorithms will depend on a large number of factors which are hard to account for in a single answer. In general terms, there are the $$O(n^2)$$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances; Quicksort, which is worst-case $$O(n^2)$$ but quite often $$O(n\log n)$$ with good constants and properties and which can be used as a general-purpose sorting procedure; the $$O(n\log n)$$ algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms; and the $$O(n)$$, or linear, sorting algorithms for lists of integers, such as radix, bucket and counting sorts, which may be suitable depending on the nature of the integers in your lists. If the elements in your list are such that all you know about them is the total order relationship between them, then optimal sorting algorithms will have complexity $$\Omega(n\log n)$$. This is a fairly cool result and one for which you should be able to easily find details online. The linear sorting algorithms exploit further information about the structure of elements to be sorted, rather than just the total order relationship among elements. Even more generally, optimality of a sorting algorithm depends intimately upon the assumptions you can make about the kind of lists you're going to be sorting (as well as the machine model on which the algorithm will run, which can make even otherwise poor sorting algorithms the best choice; consider bubble sort on machines with a tape for storage). The stronger your assumptions, the more corners your algorithm can cut. Under very weak assumptions about how efficiently you can determine "sortedness" of a list, the optimal worst-case complexity can even be $$\Omega(n!)$$. This answer deals only with complexities. Actual running times of implementations of algorithms will depend on a large number of factors which are hard to account for in a single answer. 1 answered Dec 2 '13 at 18:58 Patrick87 11.9k11 gold badge3535 silver badges7272 bronze badges In general terms, there are the $$O(n^2)$$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances; Quicksort, which is worst-case $$O(n^2)$$ but quite often $$O(n\log n)$$ with good constants and properties and which can be used as a general-purpose sorting procedure; the $$O(n\log n)$$ algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms; and the $$O(n)$$, or linear, sorting algorithms for lists of integers, such as radix, bucket and counting sorts, which may be suitable depending on the nature of the integers in your lists. If the elements in your list are such that all you know about them is the total order relationship between them, then optimal sorting algorithms will have complexity $$O(n\log n)$$. This is a fairly cool result and one for which you should be able to easily find details online. The linear sorting algorithms exploit further information about the structure of elements to be sorted, rather than just the total order relationship among elements. Even more generally, optimality of a sorting algorithm depends intimately upon the assumptions you can make about the kind of lists you're going to be sorting (as well as the machine model on which the algorithm will run, which can make even otherwise poor sorting algorithms the best choice; consider bubble sort on machines with a tape for storage). The stronger your assumptions, the more corners your algorithm can cut. Under very weak assumptions about how efficiently you can determine "sortedness" of a list, the optimal worst-case complexity can even be $$O(n!)$$. This answer deals only with complexities. Actual running times of implementations of algorithms will depend on a large number of factors which are hard to account for in a single answer.