Interesting that this and the OP's solutions result in different answers.

Ken and Dylan's solution is brilliant, and readable, but has a lot of magic. Don't be surprised if you read (and run!) their solution end-to-end, understanding each piece, but still don't believe that the whole thing works!

(Note, the solution is in 4 parts, but Part 4 is not in the table of contents.)

First, understand that it relies on Haskell's built-in (implicit/invisible) theorem-prover, lazines, and purity to work. It is not possible to directly translate their code into (much uglier) code in C/Python/Java and expect is to work.

Second, while they tersely explain all the math they use, like "automatic (formal) differentiation", "seminearring", it really helps if you are already familiar with these concepts from a college "modern algebra" class, in order to maintain the intuition in your head to follow the exposition.

Third, a lot of the magic of Haskell isn't explicitly explained in their blog post, such as:

0. Where is the, um, "execution" ("main" function)? When not using the IO monad or other explicitly sequential operations, Haskell programs do not have any instructions (loops or command statement), only declarations and definitions/assigments. The only "instruction" in the program is the command to print the value of a function on the console. Haskell's built-in call-by-need need-resolution engine then does all the work of deciding which functions need to be called in which order to compute and print the one top-level function.

1. why differentiation works to solve this problem (Part 2). (The reason is not hard to see if you play with the functions, but is hard to see just by reading: The concrete examples of string lists are all in section 1, but differentiation is defined in section 2, and they don't show any examples of differentiation applied to concrete lists of strings.)

2. Why summing over vast trees is efficient. (Part 2 and Part 3) Each node in the tree contains a reference to (basically) a small function, describing how to combine its branches. That function is collapsed to a value the first time it's value is needed (Haskell's lazy call-by-need semantics).

Note that the tree is extremely redundant! It contains something like (but not quite) log (n) distinct nodes in a tree of n total nodes representing n integeres. The use of indirection, which is implicit in Haskell (like Java!), means that by computing the a sum over part of the tree, we get many other computations for free, even though the code superficially appears to copying values.

Haskell's purity (and therefore, equivalence between functions and their results), means that each function call (including arguments is only ever evaluated more than once, without any explicit visible coding of that evaluation+memoization (not like Java).

3. Why sorting is efficient. The reason is basically the same as why summing is efficient (above).