Algorithms for Life: Sorting & Caching

So picture this. It is Sunday evening. Right. OK. Setting the scene. Yeah. And you are sitting there at your desk looking at this just like sprawling to do list for the week ahead and you decide OK it's time to finally get organized. Right. You figure it'll take maybe 20 30 minutes to prioritize everything but then three hours later you are literally still agonizing over whether like reorganizing your inbox is more important than drafting a quarterly report. Oh yeah. Or you know if paying the utility bill should come before or after scheduling the dentist. And it just feels like a personal failing right. Like you just lack discipline. Exactly. But but the truth is you're actually locked in this battle with a fundamental law of the universe. We really the universe. Yeah. I mean the friction you feel in that moment isn't a lack of willpower at all. It is a mathematical wall. And to really understand it we have to look at this paper published in 1959 by two mathematicians Lester Ford Junior and Selmer Johnson. OK. 1959. What were they looking into. So they presented what seemed like a very you know tidy little puzzle. They basically just wanted to know how to rank contestants in a tournament using the absolute fewest possible head to head comparisons. That was it. Just a simple tournament bracket problem. Right. But here's the wild part. Sixty five years later nobody has completely solved their problem for large numbers. Wait still. Nobody solved it. Nobody. And the reason it remains unsolved is that buried inside their work is this information theoretic proof. It proves there is a hard mathematical floor on how much work it takes to put things in perfect order. So it's not just that organizing takes time. It's that like the universe literally doesn't offer a shortcut. None at all. In computer science this principle was later formalized by Donald Knuth in 1998 and it's known as the N log and lower bound the N log and lower bound. OK let's unpack that a bit. Let's break down the mechanics of why this happens. Imagine you have a certain number of tasks on your desk. Let's call that number N. The total number of possible ways you could order those tasks is N factorial. Right. The factorial math. Exactly. So if you have just three tasks there are six possible ways to rank them. But factorials grow astronomically fast. If you have five tasks there are 120 combinations. If you have 10 tasks there are over 3.6 million possible orderings. 10 tasks. I mean that's just the standard Tuesday morning and you're saying there are 3.6 million ways to prioritize just those 10 things. Over 3.6 million. Yes. And here is the core mechanism of the trap. Every time you compare two tasks asking yourself you know is task A more important than task B you extract exactly one single bit of yes or no information. Just one bit. Yeah. So to sit through 3.6 million possibilities and mathematically isolate the one perfect ranking you have to extract a massive number of bits. The minimum number of comparisons required grows at the rate of N times the logarithm of M. Wow. Which means if you double the size of your to do list you don't just double the time it takes to prioritize it. You like exponentially increase the effort. That right there is the mechanism behind the Sunday night struggle. Every single item you add to your life increases the mathematical burden of organizing it. It really does. So for this deep dive into the research dossier we are going to explore what the mathematics of sorting and caching can actually teach us about organizing our own lives. And maybe more importantly when the science says we need to just stop organizing altogether. Because I mean if perfect sorting is mathematically exhausting we have to look at how systems actually survive this bottleneck. Like how do our computers handle information retrieval so incredibly fast if the underlying math is so hostile. Well there's actually a real world equivalent to how you bypass that math. Think about how an emergency room works. Oh that's good analogy. Yeah. When 50 people are in the waiting room the triage nurses don't run a comparison sort. They don't look at every patient and ask is the broken arm worse than the sprained ankle but better than the flu. Because that would trigger the N log N trap and take hours. Exactly. Instead they use what computer scientists call a Robotska sort. They just bypass comparison entirely and bucket people by broad categories like critical urgent or stable. It's classification not sorting. Right. Exactly. Computers bypass the bottleneck using a similar philosophy of structure specifically through a memory hierarchy. You know they use layers. And this brings us to one of the most eye opening pieces of data in the dossier. Google engineers Jeff Dean and Peter Norvig mapped out the latency numbers for the different layers of computer memory. Yes. Latency table. Usually these are measured in nanoseconds which let's be real the human brain can't really visualize. But to make the mechanics comprehensible they multiplied all those durations by a billion scaling them up to human time. The scale that makes the architecture completely tangible. Yeah. So in a computer the fastest memory which sits right next to the processor is the L1 cache at human scale. Grabbing a piece of information from the L1 cache takes about half a second. So just a single heartbeat. Yeah a heartbeat. The next layer out is the L2 cache. Retrieving data from there takes about seven seconds which is roughly the length of a long yawn. OK. A moving further out to main memory fetching data takes about a minute and 40 seconds. Yeah. Think of that as the time it takes to brush your teeth. Got it. And then there is the hard drive right. The cold storage. Oh yeah. If the computer has to do a disk seek like reaching all the way into the deep archives just to retrieve one tiny piece of information at human scale that takes 16 and a half weeks. Yeah it's wild. You could literally enroll in a university in September attend all the lectures take your final exams in December and the computer would finally hand you the file you asked for. And the overlap with cognitive science is striking here. Human working memory you know the mental workspace where you hold the active thoughts you need right this second is your biological L1 cache. It is brutally small. It can hold maybe five to seven items but your access to those items is instantaneous. On the other end your long term memory is your disk storage. Its capacity is functionally infinite but transferring information in and out requires intense effortful encoding. We've all felt the pain of a slow disk read in our own brains haven't we. Definitely. Like when you are trying to remember the name of an actor and it's right on the tip of your tongue but you just can't pull it. A 2020 fMRI study actually monitored people in that tip of the tongue state. Oh right. The fMRI scans. Yeah. Their prefrontal cortex was lighting up burning massive cognitive resources. Your brain is literally stuck waiting weeks in human scale time for the data to load from cold storage which means the speed at which you operate isn't determined by how fast your brain processes information but by how well you manage what lives in your fast cache versus your slow storage. That makes total sense. And this constraint inspired a massive algorithmic breakthrough in 2002. A software engineer named Tim Peters was trying to make the Python programming language sort data faster. Oh this is Tim sort. Yes. The result was Tim sort which is now the default sorting algorithm in Python Java Android and Chrome. I love the philosophy behind Tim sort. Essentially it's lazy. Like let's use an analogy. Imagine Marie Kondo coming into your house to help you organize. Her method is to pull every single book shirt and paper onto the living room floor and start from scratch. Right. Which in computer science that is a full comparison sort on your entire data set. It triggers that factorial math we talked about. Exactly. Tim sort on the other hand says hey the books on the shelf are mostly grouped by author already. Just tidy up the edges. Yeah. The mechanism that makes Tim sort so efficient is that it actively scans the data looking for pre-existing order what Tim Peters called natural runs natural runs. Right. Because real world data is almost never truly random. Your email inbox arrives roughly in chronological order. Right. Tim's word exploits the structure of the environment instead of fighting it. It stitches together the order that is already there. But wait if I apply that to my own physical space like my desk or my office just leaving things where they lie and tidying the edges sounds like a recipe for a nightmare. You think so. Yeah. I mean without a meticulously structured filing system with proper folders how do you actually find anything when you need it. I'm looking at the UK government's UX research in our dossier the dot UK study. Yeah. They found that pure search completely fails when users don't know the right vocabulary to search for. If I don't know the exact legal name of my tax document a search bar is basically useless. Doesn't a system without folders just break down. It's a common fear but the data on personal productivity actually points the other way. Let's look at Thomas Malone's 1983 study published in the ACM Transactions on Information Systems. OK. What did he find. He researched how people organize their physical desks. He found that the chaotic looking piles of paper on workers desks weren't messes at all. They were spatially instantiated LRU caches LRU caches. Yeah. LRU stands for least recently used. The mechanism is brilliantly simple. Every time you touch a paper you put it back on top of the pile. Over time the stuff you use most naturally rises to the top and the stuff you haven't touched in months sinks to the bottom. So the pile is actually a self sorting machine driven by your own behavior. That's fascinating. Exactly. And Malone found something even more surprising about the alternative. He discovered that hierarchical filing systems carry a massive ambiguity cost ambiguity cost. Yeah. The people who diligently filed every paper often couldn't find their own documents months later. The reason is that when you file something you have to guess how your future self will look for it. If you have a folder for finances and a folder for house projects where do you put the invoice for the roof repair. The brain just freezes. Oh I see. You pay the cognitive cost of classifying the item when you file it and then you pay it again when you try to retrieve it because you have to basically reverse engineer your own logic. Furthermore a 2019 management science study analyzing chaotic warehouse storage found that deliberately placing dissimilar items together as long as you have a system to search for them actually increased order fulfillment productivity. Really. Chaotic storage won. Yes. By roughly 5 percent over meticulous categorized sorting. Wow. I see the mechanics of why that works now. In personal information management they call this premature filing. Right. If you painstakingly sort every single email and receipt into 50 different sub folders you are paying the in log in classification cost on 100 percent of your items. But realistically you are only ever going to need to retrieve maybe 5 percent of them. Exactly. It's a massive waste of human energy. So the resolution to the GOP dot UK finding seems to be a hybrid. You need a taxonomy or folders for browsing when you are exploring a new topic and don't know the vocabulary. But for your own personal files known items approximate placement combined with a good search bar is vastly superior. That is the takeaway. Sorting your personal life is essentially a bet on your future queries. And honestly most of us are terrible bookmakers. But if perfect sorting is mathematically broken and meticulous filing is mostly wasted effort what are we actually trying to achieve here. What is the goal of organizing our lives. The goal is satisfying. Satisfying. Yes it's a term coined by Herbert Simon. Blending the words satisfy and suffice. And the concept that good enough beats perfect isn't just a self-help slogan, it is the most robustly verified claim in our entire research dossier. Wow, really? It converges across four completely independent scientific traditions. We've seen it in computer science complexity theory with the n-log-n barrier. In behavioral economics, Herbert Simon actually won the 1978 Nobel Prize, partly for proving that humans operate on bounded rationality we satisfy. And in operations research, we just saw it with chaotic warehouse storage beating perfect categorization. And the fourth tradition is cognitive psychology, right? Gerd Gigerenzer's work with the ABC Research Group in 1999. Yes, you've got it. They demonstrated a heuristic called take the best. They proved that in noisy, unpredictable environments, making a decision based on just one single reliable cue often matches or even beats complex statistical models that try to weigh a dozen variables. The mechanism there is the bias-variance tradeoff. When you build a complex model, it tends to overfit the past data, making it super fragile when predicting the future. Simple models are just more robust. OK, but let me challenge the broader philosophy of satisficing, though. Isn't good enough just like an academic excuse for lowering our standards? Because if I'm a structural engineer, I definitely don't want to design a satisfied bridge. If I'm a surgeon, I don't want a satisfied procedure. In the real world, excellence matters. That tension is real, absolutely. But it's resolved by understanding the scope of the principle. Satisficing is specifically designed for environments where the cost of finding the optimum answer exceeds the value of actually having it. Ah, so it's about reversible, low-stakes decisions. If the bridge fails, people die. That is an irreversible high-stakes domain where optimization is totally required. But if you miscategorize a to-do list item, the stakes are zero. The cost of perfectly prioritizing your weekend tours wildly outweighs any benefit you get from having them perfectly prioritized. Yes, and knowing the boundary between those two domains is the actual skill. Which means we can apply a simple test. Identify the minimum acceptable outcome for organizing your desk. The moment you hit that threshold, the moment you can generally find what you need, you stop optimizing. You just walk away. Right. OK, so we've accepted that our organization should just be good enough. We rely on search, and we let piles naturally form based on what we use. But there's a physical reality here. Over time, our fast-access systems fill up. The desk gets covered in coffee cups and old mail. The inbox overflows. How do we keep the system from just collapsing under its own weight? By understanding that memory management is mostly about what you throw away. You have to implement cache eviction. Cache eviction. Yeah, every fast-access memory system has an eviction policy. A set of rules dictating what gets removed when the space is full. We mentioned the LRU policy earlier, least recently used. It's highly effective, but it has a fatal vulnerability. It can be poisoned by a sequential scan. A sequential scan, meaning if I suddenly decide to look through 3,000 old vacation photos from 10 years ago, I flood my fast memory. Yes. Because those photos are now technically the most recently used items, the algorithm pushes out the active projects you actually need for work tomorrow, replacing them with old photos you won't look at again for another decade. The cache becomes polluted. So how do computers fix that? With an incredibly elegant solution created by IBM researchers Nimrod Megiddo and Dharmendra Moda in 2003. It's called the ARC Algorithm Adaptive Replacement Cache. Okay, ARC. How does it work? Well, the mechanism that makes ARC special is something called a ghost cache. When the fast memory is full and the algorithm has to evict a file, it throws the file away, but it leaves behind a tiny, weightless marker, a ghost. It remembers what it evicted. Oh, I see. Yeah. And if you suddenly ask for that file again a few minutes later, the algorithm checks the ghost cache, realizes it made a mistake by evicting it too early, and learns from that error. It adjusts its rules on the fly to balance recency with frequency. Wow. The ghost cache is literally a someday maybe list. You evict a task from your active view to clear up your mental L1 cache, but you keep a lightweight ghost entry on a backburner list just in case it becomes relevant again. Exactly. This fundamentally changes how I view Merlin Mann's concept of Inbox Zero from 2006. Oh, the cultural misunderstanding of Inbox Zero is fascinating. It really is. Everyone thought Mann was preaching moral superiority, that if your inbox was empty, you were a better, highly effective person. But if you look at the underlying theory, he was just describing a strict eviction policy. Your email inbox is what computer scientists call a bounded buffer. It has a limit, and every item that enters that buffer must pass through a finite state machine, meaning you don't just stare at the email, you run it through a rigid set of tracks. It can only go to one of five destinations, reply, archive, defer, delegate, or delete. That's it. So a full inbox isn't a failure of discipline. It is literally just a cache overflow event because your eviction policy is broken. That finite state machine works perfectly for moving data. But when we apply this to human psychology, when we constantly offload our thoughts into these external systems, we run into a serious biological tension. Really? I always thought writing things down was pure upside. Like, Messicompo and Baumeister published a landmark 2011 study in the Journal of Personality and Social Psychology showing the power of cognitive offloading. It did, yes. They found that simply making a concrete plan for a task neutralizes the Zygarnik effect. You know, that nagging, stressful feeling your brain gives you when you leave a task uncompleted. Writing it down tricks the brain into letting go. It absolutely relieves the stress. But the newer research on cognitive offloading reveals a hidden cost. Studies show that people who routinely rely on external tools to store information demonstrate measurably lower memory performance for that specific content later. Lower memory performance? Yeah. Your brain is highly efficient. If it knows the information is safely stored in a digital notebook, it biologically stops spending the energy required to encode it into your long-term memory. Wow. You are trading stress relief for actual memory formation, so treating your productivity system as a temporary cache is brilliant, but using it as a total replacement for your own memory is a trap. Exactly. If something truly matters, a core skill, a relationship detail, a critical piece of knowledge, you still have to do the hard work of intentionally promoting it to long-term memory. Which gives us a very practical threshold. If your active inbox or your daily to-do list exceeds 20 or 30 items, treat it as a cache overflow. Do not try to type faster or work harder. The system is telling you to adjust your eviction policy. Alright, we have unpacked the mathematical impossibilities of sorting, the human-scale latency of our memory, the futility of perfect filing, and the necessity of cache eviction. How do we actually synthesize all of this into action? Right, let's get practical. We pulled a concrete four-week protocol from the dossier to help you implement this starting Monday morning. So week one is the audit. You need to identify your L1 cache, the spaces you access instantly. This is the physical surface of your desk, your computer's desktop screen, and your phone's home screen. The rule is simple, evict anything you do not use on a daily basis, push it to slower storage. Love that. Then week two is classify. We are going to kill the comparison sort. Stop triggering the n-log-n mathematical trap by agonizing over whether task A is more important than task B. Right, no matter that. Use the emergency room radix sort instead. Create three broad buckets, active this week, active this month, and archive, and just toss things into them. Let the natural piles form. Week three is the single-pass protocol. We apply the finite-state machine to your bounded buffers, like your email or your mail pile, process it twice a day, touch every item exactly once, route it through one of the five actions, reply, archive, defer, delegate, or delete, and move on. And week four is evict. You are going to run what computer scientists call a CLOCK algorithm sweep on your system. The CLOCK algorithm, right. Imagine a clock hand sweeping in a circle over all your commitments. As it passes each item, it checks for a single piece of data, a recently used flag. If you haven't engaged with that project recently, the clock hand sweeps it into the trash. And regarding that active deletion, I really want to highlight a 2018 study from Frontiers in Psychology on intentional forgetting. Okay, what's that? They found that when organizations attempt to implement new routines, the failure rarely happens because people cannot learn the new way. The failure happens because they cannot forget the old way. The mechanism for true behavioral change requires actively removing the cues that trigger old habits. You can't just ignore the old newsletters. You have to unsubscribe. You have to delete the desktop shortcuts. Intentional forgetting requires active deletion. Which means the weekly review you do on Friday afternoons isn't just about planning, it is fundamentally a heap rebuild operation. You are sweeping the floor, dumping the useless data, and restructuring your priorities so the most important things float back to the top of the pile. That's beautifully put. We spend so much time and money adding to our systems, buying better apps, creating more folders, getting bigger hard drives, but a system that only adds and never removes will inevitably collapse under its own weight. Eviction isn't a failure to keep up. Eviction is a feature that keeps the system alive. Absolutely. And as we wrap up this UW research deep dive, we really need to return to where we started. Ford and Johnson's 1959 tournament problem. Right. 65 years later, nobody has proven whether their algorithm for sorting things with the absolute minimum comparisons is truly optimal. And honestly, that lack of a perfect answer is the deepest lesson here. It really is. The quest for perfect organization has a provable mathematical cost, and past a very early point, that cost aggressively exceeds the benefit. The unsolved problem in computer science is the exact same unsolved problem on your desk. The answer in both cases is not try harder or buy a new planner. The answer is knowing when good enough is good enough. So let's synthesize the three core takeaways for you to carry forward. First, good enough beats perfect. This is not an excuse for laziness. It is the principle of satisficing independently verified by four separate scientific traditions. Right. Second, the question isn't how to sort better, but whether you should be sorting at all. Sort less, search more. Rely on approximate placement until your retrieval demand proves that a folder is strictly necessary. And third, what you choose to discard is what makes your memory functional. Eviction is a feature, not a failure. Active deletion is required to keep both your computer and your brain operating at speed. And this brings up a provocative thought that builds on everything we've just talked about. If human memory has a strict L1 cache limit and intentional forgetting is required for functional systems, think about our social media feeds. They are effectively systems with zero eviction policies. Oh, that's a great point. We're trying to maintain a human scale memory hierarchy for thousands of casual acquaintances we haven't spoken to in a decade. Maybe the ultimate application of the CLOCK algorithm isn't just your inbox, but your social graph. It's just something to mull over. If this deep dive changed how you think about organization, share it with someone who is drowning in their inbox or fighting a losing battle with their to-do list right now. And for more briefings like this one for you to research, plus the full annotated dossier containing every study and algorithm we cited today, head over to udame.ai.