I want to sort the numbers using linked list in O(nlogn) time complexity and O(1) space complexity? Plz help me in this.
→ Pay attention
Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 days
Register now »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 days
Register now »
*has extra registration
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/21/2024 09:32:36 (i2).
Desktop version, switch to mobile version.
Supported by
Use merge sort: If your list is empty or contains single element, it is already sorted, otherwise split it into two equal parts, sort them recursively and merge into single sorted list.
Yes, but how to maintain O(1) space complexity, thats the only issue I am facing. Can you plz provide me link where I can find code or explanation of how to maintain O(1) space complexity( meeting O(nlogn) time complexity).
Do you have a linked list or array? The former allows you to re-arrange, insert and remove elements arbitrary in O(1), the latter does not (but it also does not require keeping a pointer to element to make any action).
Simple implementation. https://gist.github.com/Norpadon/410649f0389749601980
This is recursive so has O(logn) space complexity
Thanks, i missed that.
Here is non-recursive version: https://gist.github.com/Norpadon/e5a9f1b1139a17a9500e
Code is a bit messy, but idea should be clear.