Timeline for Best time complexity of sorting numbers in range [1...n log n]
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2018 at 13:18 | answer | added | Thinh D. Nguyen | timeline score: 0 | |
| Sep 21, 2018 at 11:41 | history | edited | xskxzr |
edited tags
|
|
| Sep 21, 2018 at 7:53 | comment | added | Bulat | @YuvalFilmus thank you, this makes sense. And now my point - in ppractice, you should use ~~256 bins to fit CPU cache structure (TLB, write combining buffers...). So you need to make O(log n) radix sort passes. In theory, you can use counting sort or fixed number of passes | |
| Sep 21, 2018 at 6:50 | comment | added | Yuval Filmus | @Bulat In the word RAM model, each memory location contains a machine word, which is $O(\log n)$ bits long (where $n$ is the input length). | |
| Sep 21, 2018 at 6:13 | comment | added | Bulat | @YuvalFilmus already found "By definition: A register is a location with both an address (a unique, distinguishable designation/locator equivalent to a natural number) and a content – a single natural number" --- of course, ability to hold ARBITRARY natural number is completely unrealistic | |
| Sep 21, 2018 at 6:07 | comment | added | Bulat | @YuvalFilmus how it works with numbers in given range? Is it suppose that each cell can hold arbitrary number? Or that each cell can hold fixed number of bits? By unrealistic I mean that radix sort on real computers became much slower when you use more than ~~256 bins in radix sort. So on real computers you will use 256 bins or so, in theoretical setting you may use O(log n) bits | |
| Sep 21, 2018 at 4:52 | answer | added | xskxzr | timeline score: 2 | |
| Sep 21, 2018 at 4:23 | comment | added | Yuval Filmus | On the contrary, the word RAM model is supposed to be more realistic than the bit complexity model. | |
| S Sep 21, 2018 at 3:35 | history | edited | xskxzr | CC BY-SA 4.0 |
Improved question title, simplified the range
|
| S Sep 21, 2018 at 3:35 | history | suggested | Bulat | CC BY-SA 4.0 |
Improved question title, simplified the range
|
| Sep 20, 2018 at 22:28 | review | Suggested edits | |||
| S Sep 21, 2018 at 3:35 | |||||
| Sep 20, 2018 at 19:40 | comment | added | Bulat | OTOH, if you process O(log n) bits on each pass, you will need to use fixed number of passes. This means using O(n) extra memory, so why not? Anyway it's pure theory which is far from real setting | |
| Sep 20, 2018 at 18:29 | comment | added | Bulat | each number has O(log n + log log n) = O(log n) bits, so radix sort requires O(log n) passes. I think the answer is incorrect since authors forgot about this part of equation. Overall, radix sort is O(n) only for fixed-size numbers. | |
| Sep 20, 2018 at 17:58 | history | edited | chendoy | CC BY-SA 4.0 |
added 7 characters in body
|
| Sep 20, 2018 at 17:53 | history | asked | chendoy | CC BY-SA 4.0 |