As the addendum to the paper points out, this is more like insertion sort (with i and j in a confusing order) than bubble sort. The actual “important” part of the algorithm happens when j < i. (In fact, I’m quite certain there aren’t even any swaps when j >= i after the first outer iteration.) (I think the page about people misremembering bubble sort is also worth looking at.)

Honestly, I think this might actually be “better” than bubble sort, in the sense that at least it’s incredibly easy to remember and not that hard to get correct. The only place where you could realistically mess up is confusing the relative order of i and j – and any amount of nontrivial testing will immediately show the error, since it reverses the sort order. I’d probably reach for this if I, for whatever insane reason, had to code up a sorting algorithm by hand for some task where O(n^2) sorting was acceptable performance-wise. “Sort a list of 10 items in a very primitive programming language”-type deal.

(Now that I say that, I’m kind of tempted to use it in some example program for my own in-development programming language, which currently doesn’t have a builtin sort function…)

There’s a good chance I can make use of str::substr_range on a current project of mine. I’ll be storing some substrings from str::split, and now I can store the original string and ranges of indices into it instead of making an owned string for every substring.

Just finished “version 0” for a very simple programming language yesterday, and I’m looking to work on “version 1” this weekend. Rust is truly fun to program in… although writing all the tests was not a very fun experience. But doing the work for that meant I was guaranteed to have a reasonably good grasp of the semantics by the time I finished.

Since it’s Rust, there’s no garbage collector – heck, for this particular language, there’s not even any memory allocation after startup. Instead you get a giant global array of “memory” to work with. The only data type is the 32-bit integer (and thus, using UTF-32 for strings is actually the """correct""" choice for this language). I’m using a vaguely Lisp-like syntax that revolves around {[a tree] formed from (brackets and whitespace)}… which was probably slightly easier to parse than more traditional syntax, but Rust’s current lack of pattern matching “through” Vec (for example, letting you extract e from {a b [c (d e)] f} in one step) didn’t always make it feel that way.

Nest up: adding while loops, exponentiation and bitwise operators, and most interestingly, string and character literals. (The char literals would just evaluate to their character codes, and string literals would only be usable in a specific write-to-memory construct.) And also expanding the standard library. I’d say “version 1” would really be the more properly “complete” version of the language. I also want to do a functional programming variation (ditching the global memory in favour of reference counted cons cells), and also the whole language is kind of just a stripped down version of another much bigger language half-formed in my head, but that’s all probably for… not this weekend, at any rate.