Website of Sebastian Wild, algorithms researcher
Simple proof that standard mergesort with a single extra comparison is run-adaptive in a rather strong sense. We consider standard top-down recursive mergesort, where we do a single comparison before calling merge, to check whether the two recursively sorted subproblems happen to already be correctly ordered. (If so, we can skip the merging step.) We show that for any input $A[0..n)$ consisting of…
GitHub blocked my account. I don’t know why or for how long. tl;dr: If you need any old repository, use the cloned versions at sebawild2 . As of now, four weeks on, GitHub still blocked by account sebawild . (It is invisible to others, but let’s me log in and access my repositories.) The overall episode is rather annoying: You get blocked and there’s no reason given. You can file a ticket, but for…
My colleague Tony McCabe put a game implementation of merging policies together, where you can try to find the minimal-mergecost order of merges. Below are a few example inputs to try. You have to drag&drop one run over one of its neighbors to merge them; this costs you the sum of their lengths. The goal is to merge up all runs with minimal total cost. Run lengths: --> Run lengths: LEGO input: 4 2…
I presented Powersort and its story at PyCon US 2023 , the largest Python community conference. Here are some resources and impressions from the last couple of days here in Salt Lake City. View on downtown Salt Lake City (with the conference venue!) and Utah State Capitol, from Ensign Peak. Resources Official Talk recording My reupload with the antiphase audio fixed Talk slides (Speakerdeck seems…
If you consider contributing sorted lists from your own Python application to our benchmark for adaptive sorting, the steps below show you how to do collect this data. Note: Our instrumentation stores a list of integers with equivalent comparison-behavior to all lists sorted when running Python code through our custom CPython. Background The goal of the benchmark is to collect real-world data from…
For experimenting with novel CPython features, you can quickly set up an isolated environment. This post shows you how to do that. I did this on Ubuntu 20.04 LTS with standard build tools installed, but the same instructions probably work more generally. Compile python Download latest CPython sources git clone git@github.com:python/cpython.git Change to a stable branch instead of main (so that we…
Our sorting method Powersort ( Wikipedia ) is used as default list.sort() algorithm in CPython, the reference implementation of the Python programming language. Join the Powersort Competition Help us study Timsort and Powersort and win substantial prizes! See my PyCon US talk for the full story. Here’s the entry from the official Python changelog : bpo-34561 : List sorting now uses the…
A rigorous proof that a stack implemented with doubling arrays has constant amortized time operations; written up here since it does not seem to appear in any of the standard algorithms books. A well-known, fundamental data structure is the implementation of a stack using resizing arrays (a.k.a. doubling arrays), where we maintain an array of $C$ items for the $n$ elements of a stack, and whenever…
Showing more than 15 recent folders in move-to and copy-to context menus is easy in Thunderbird 91. I’m a heavy user of many IMAP folders for organizing email (and Günter Gersdorf’s brilliant Thunderbird extension Copy Sent to Current ), moving emails to folders quickly is important. Thunderbird long has remembered which folders were used most recently, offering to move or copy mails there in a…
I describe my solution for online lecturing amid the COVID-19 crisis using youtube livestreams and PINGO. Although I kind of saw it coming after reading this excellent data analysis (on March 12, before things got really crazy), things did get hectic: The official decision of University of Liverpool to move all face-to-face classes online with immediate effect came on Saturday evening (March 14),…