search

roarin-roran / Sorting

0 stars 0 forks source link

memory management for top down #68

Open roarin-roran opened 2 years ago

roarin-roran commented 2 years ago

current k-way peeksort code uses self.input_list as a globally correct state of the order of things, requiring merges to be copied in from a temporary list at potentially unnecessary cost.

update this by using an alternative memory management strategy that avoids the extra copies.

note - this would be a strict improvement to any top down sorting method that we know about, and a little bit of a coup if we can get it working

bens candidate answer (to be thought more about): use ping pong, where read_ping_write_pong is true when the depth is even, and false when the depth is odd. may be doable, tricky, or impossible - either way, I'll investigate it

roarin-roran commented 2 years ago

(note to self: search #pingpongdiag in chat with sebastian to get the diagram I was thinking of using)