Search
Wednesday, 14th of November 2018, 15:49:54 UTC
15:50:02
shka_
ACTION waves hands around
15:51:35
jcowan
Most list sorts are list->vector, vector sort, vector->list, which is disturbingly non-optimal
15:52:35
shka_
jcowan: IIRC beach was talking about sorting vectors, specificly
15:53:25
beach
Yes, sorting a list using merge sort is trivial in O(n long n) time and O(1) space.
15:53:56
beach
It is fast and stable. Converting it to a vector would be worse.
15:54:42
shka_
beach: quick googling shows that those are not the algorithms i seen recently
15:55:08
shka_
are you intersted in even better algorithm for in-place merge?
15:55:19
shka_
does not work on all sizes
15:55:39
shka_
so it is slightly more difficult to implement
15:56:49
beach
shka_: I am, but I am only collecting documentation at the moment. I have no time to even think about sorting right now.
15:57:21
shka_
well, that's fine, i think that this one is worth collecting
16:00:30
shka_
https://ac.els-cdn.com/S1877050910005478/1-s2.0-S1877050910005478-main.pdf?_tid=4398908f-dfbf-4465-b074-8a0320bfa7dd&acdnat=1542211323_ed2db6f6133a7976bb324bcdedff783e
16:01:05
shka_
beach: just in place merge, but idea is cute and probabbly useful
16:02:54
jcowan
https://www.sciencedirect.com/science/article/pii/S1877050910005478 is a more canonical URL
16:03:29
beach
shka_: Looks interesting. I would want the taker of the challenge to implement several algorithms and compare them, of course. And perhaps even combine them in interesting ways, depending on the situation.
16:04:47
shka_
beach: i will take a shot at the algorithm i pasted on weekend
Thursday, 15th of November 2018, 3:49:54 UTC