Loading...
Please wait, while we are loading the content...
Similar Documents
Sorting In-Place with a Worst Case Complexity of n log n − 1 . 3 n + O ( log n ) Comparisons and ε n log n + O ( 1 ) Transports ∗
| Content Provider | Semantic Scholar |
|---|---|
| Author | Reinhardt, Klaus |
| Copyright Year | 1992 |
| Abstract | First we present a new variant of Merge-sort, which needs only 1.25n space, because it uses space again, which becomes available within the current stage. It does not need more comparisons than classical Merge-sort. The main result is an easy to implement method of iterating the procedure in-place starting to sort 4/5 of the elements. Hereby we can keep the additional transport costs linear and only very few comparisons get lost, so that n log n − 0.8n comparisons are needed. We show that we can improve the number of comparisons if we sort blocks of constant length with Merge-Insertion, before starting the algorithm. Another improvement is to start the iteration with a better version, which needs only (1+ε)n space and again additional O(n) transports. The result is, that we can improve this theoretically up to n log n − 1.3289n comparisons in the worst case. This is close to the theoretical lower bound of n log n − 1.443n. The total number of transports in all these versions can be reduced to ε n log n+O(1) for any ε > 0. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www-fs.informatik.uni-tuebingen.de/~reinhard/sort.pdf |
| Alternate Webpage(s) | http://www-ti.informatik.uni-tuebingen.de/~reinhard/sort.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
