miniblog.

← Back to all posts
Jan 14, 2013 at 17:47
There is no sorting algorithm that is O(n log n) in time, O(1) in space and also stable. Pick your poison.

Related Posts

Mar 10, 2025 at 07:03
12
Spent a bunch of time learning about text diffing algorithms this evening. "Myers Algorithm" refers to a specific paper written by Eugene Myers, and he published faster algorithms later!
LCS Algorithms
LCS Algorithms
a structural diff that understands syntax 🟥🟩. Contribute to Wilfred/difftastic development by creating an account on GitHub.
Nov 7, 2023 at 01:35
There's a class of performance bugs that you can feel. Today I inadvertently implemented "Schlemiel the Painter's algorithm", and it's obvious: performance was great at first, and then it gradually deteriorates.
Jan 15, 2023 at 09:21
Today I learnt about a cunning trick used by GNU diff to make Myer's algorithm faster: https://github.com/mitsuhiko/similar/issues/15 If you do an initial pass to find items that only occur on one side, you can discard them before diffing! They'll always be shown as changed.
Implement Myers Heuristics · Issue #15 · mitsuhiko/similar
Implement Myers Heuristics · Issue #15 · mitsuhiko/similar
GNU diff and others have some internal heuristics to bail if there are too many changes. There are basically two optimizations: Discard lines which are completely distinct between two files: this h...