3 ms·

Interesting approach, although I'm wondering why they didn't just use a double-ended queue instead of a linked list. Also, I get the urge to name the algorithm

Interesting approach, although I'm wondering why they didn't just use a double-ended queue instead of a linked list. Also, I get the urge to name the algorithm after yourself, since Timsort is named after its creator as well, but if you call you data structure "rainbow" then my first association would be the rainbow flag, since flag-sorts also have a tradition in sorting algorithm names. [0] https://en.m.wikipedia.org/wiki/Dutch_national_flag_problem https://en.m.wikipedia.org/wiki/Dutch_national_flag_problem [1] https://en.m.wikipedia.org/wiki/American_flag_sort https://en.m.wikipedia.org/wiki/American_flag_sort

ipsum2 2y ago
First thing I think about with "rainbow" and "data structures" is rainbow tables.
blibble 2y ago
a double-ended queue is often implemented using a doubly linked list (like the one in use here) if you back it by two arrays then you can't do O(1) inserts in the middle (like is going on here)
- tialaramex 2y ago
  It's true that awful Deque implementations are often built from a linked list. If you're taught about big-O notation and haven't noticed how modern computers work you might even do that today. I would expect that they're thinking of something more like Rust's VecDeque, so that's a conventional "growable array" (Rust's Vec, Java ArrayList, C++ std::vector) used internally with some head + tail tracking to form a circular buffer so as to deliver the Deque API (fast push to head or tail, fast pop from head or tail).
  - blibble 2y ago
    you can make mechanically sympathetic linked lists with low constant factors as long as you avoid pointers
    - vanderZwan 2y ago
      Do you mean using indices into a backing array instead of pointers if the maximum length is known to be small? That probabdy helps but still has the cache issue to some degree no? (also I feel like this is arguing semantics a bit, but I'm sincerely wondering: is a linked list without pointers still a linked list?)

ipsum2 2y ago

First thing I think about with "rainbow" and "data structures" is rainbow tables.

blibble 2y ago

a double-ended queue is often implemented using a doubly linked list (like the one in use here) if you back it by two arrays then you can't do O(1) inserts in the middle (like is going on here)

tialaramex 2y ago
It's true that awful Deque implementations are often built from a linked list. If you're taught about big-O notation and haven't noticed how modern computers work you might even do that today. I would expect that they're thinking of something more like Rust's VecDeque, so that's a conventional "growable array" (Rust's Vec, Java ArrayList, C++ std::vector) used internally with some head + tail tracking to form a circular buffer so as to deliver the Deque API (fast push to head or tail, fast pop from head or tail).
- blibble 2y ago
  you can make mechanically sympathetic linked lists with low constant factors as long as you avoid pointers
  - vanderZwan 2y ago
    Do you mean using indices into a backing array instead of pointers if the maximum length is known to be small? That probabdy helps but still has the cache issue to some degree no? (also I feel like this is arguing semantics a bit, but I'm sincerely wondering: is a linked list without pointers still a linked list?)