I always saw the hormones that regulate our emotions as primitive forms of memory, older than neurons. So an organism can remain in a certain state for a while.
There is also the possibility that RNA is used for memory:
That was a great article! The last paragraph, however:
"By the way, Knuth is interested in these algorithms mainly for the interesting mathematical problems (...) not because they’re in any way efficient algorithms! "
Made me wonder, these kind of algorithms, where there is a lot of comparing and swapping of adjacent records might be more efficient on a tape-based architecture. Or an architecture with a lot of prefetch caching.