Twitter
Sorting a group of elements means placing them in an order of importance. In computer programming, sorting can be either ascending (increasing order of importance) or descending (decreasing order of importance). Further sorting algorithms can be categorised into comparison sorts and linear-time sorts. Comparison sorts use a comparison between the elements such as a<b or a>b to sort the elements whereas linear-time sorts do so in a direct placement manner. Comparison sorts have the disadvantage that they cannot break their limit of O(n logn) time whereas linear-time sorts can be applied only to group of elements which follow some specific required characteristics (eg: only being able to work on integer data). Also when we select a sorting algorithm for our purpose, the amount of space required during the sorting is considered. Some sorting algorithms sort in-place i.e they sort within the same memory space as the original elements whereas some other algorithms require allocation of new space for the sorting and then copy the sorted elements back to the original space.
Below is a table showing some of the available sorting techniques and their complexity.
| Time | |||||
|---|---|---|---|---|---|
| Sort | Average | Best | Worst | Space | Comment |
| Bubble sort | O(n^2) | O(n^2) | O(n^2) | In place | |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | In place | |
| Insertion Sort | O(n^2) | O(n) | O(n^2) | In place | |
| Heap Sort | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | In place | |
| Merge Sort | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | Extra space | |
| Quicksort | O(n*log(n)) | O(n*log(n)) | O(n^2) | In place | |
| Counting sort | O(n+k) | O(n+k) | O(n+k) | Extra space | k = max element |
| Radix sort | O(pn+pk) | O(pn+pk) | O(pn+pk) | Extra space | p = number of digit positions, k = radix |
The sorting techniques are used in file systems to display files in a sorted order, in binary searches input data is required to be sorted, etc.
Related Posts:
Tags: programming
An interesting comparison, however in place merge sort is possible. Let me know if you want need a reference for the paper.
Shell Sort and Comb Sort might be of interest. I usually use Comb Sort.
[Reply]
Kevin Reply:
January 10th, 2010 at 4:16 am
Thanks for the comment, John
It would be nice to get that reference.
[Reply]
This paper describes two versions of in-place mergesort:
Katajainen, J. “Practical In-Place Mergesort.” Nordic Journal of Computing (1996).
Available online at http://www.diku.dk/~jyrki/Paper/mergesort_NJC.ps
[Reply]
Kevin Reply:
January 10th, 2010 at 9:17 am
Thanks for the link.
[Reply]