Work in progress. Almost all are from Wikipidia:
Quicksort is often faster in practice than other algorithms.
The steps are:
Pick an element, called a pivot, from the list.
Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
“Merge sort does about 39% fewer comparisons than quicksort does in the average case; merge sort always makes fewer comparisons than quicksort, except in extremely rare cases”
Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.
Merge sort is highly parallelizable. The drawback is that it requires locations if implemented not-in-place which is more complicated.
This entry was posted in Uncategorized
. Bookmark the permalink