Timeline for Sorting an array of positive integers including 0 much faster than Radix Sort
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 10, 2021 at 18:10 | comment | added | Redu | @Norhther The code that you see has nothing to do with Radix sort but the real question is, under the hood how exactly the sparse array indices end up being served in an orderly fashion. This... most possibly turns out to be Radix Sort implementation of V8 engine that kick in when things happen. You may read my self answer below for more information. | |
| May 10, 2021 at 18:06 | comment | added | Norhther | @Redu I don't think this is Radix (I mean the algorithm, not the actual implementation). I think this is just the natural improvement of Counting Sort, just storing the actual elements and not the full range | |
| May 10, 2021 at 18:01 | comment | added | Redu | @Norhther Well it is and it is not. It seems to be a union of Radix Sort and Count Sort. You may read more in my self answer. Especially the last paragraph. | |
| May 10, 2021 at 17:51 | comment | added | Norhther | I'm afraid this is a modification of the counting sort | |
| May 10, 2021 at 17:08 | comment | added | Redu |
@Blindman67 Yes that seems to make difference however there many curious things in play (Chrome or new Edge). You may test radixSort against sparseSort on dev tools snippets with performance.now() and try data = $setOf(12500, () => $randI(12500)) anddata = $setOf(13000, () => $randI(13000)) to notice a huge difference. Apart from such breaking points Radix Sort and Sparse Sort give very close results however when you enforce duplicates like data = $setOf(12500, () => $randI(125)) then it suddenly becomes a different game.
|
|
| May 10, 2021 at 14:19 | comment | added | Blindman67 | The radix sort in jsben.ch/s6Ld2 is very poorly written. This jsben.ch/96YZc bench has a better (not best) example of a radix sort | |
| May 10, 2021 at 12:30 | answer | added | Redu | timeline score: 0 | |
| May 10, 2021 at 6:00 | history | tweeted | twitter.com/StackCodeReview/status/1391634126835486723 | ||
| May 10, 2021 at 2:44 | history | became hot network question | |||
| May 9, 2021 at 20:02 | answer | added | Cedric | timeline score: 5 | |
| May 9, 2021 at 18:40 | history | asked | Redu | CC BY-SA 4.0 |