Equal time per iteration assumption is bogus. No one would code it that way. Obvious comment but I'm not going to sort the 4-digit sock puppet comments. Sufficient to note that the first one is such.
Is the purple curve wellbb defined? It seems to be "continous line, always above the vertical lines, as close as possible, always growing"? Maybe this should have been mentioned early on, for now the definition of the purple line is...but we'll come back to this".
Your assertion that purple line has to end up on the green line eventually didn't make sense until I want thought about it. Everything else was crystal clear. The way I think of it is that the last item in the purple sublist is sorted exactly when it connects with the green line.
11:27 this way of reasoning (going to a simple case where N is arbitrarily large and learning about the rest of the domain from there) is similar to how we Christians reason by going to God first, then learning about the rest from Him.
My favourite part about this video is not the bubble sort curve solution, but how harmoniously it illustrates that the *real* intellectual leap is figuring out how to formulate a problem into something one can hold on to and tackle in bits.
There's a derivation in my previous video about the factorials/gamma function. It starts at 22:16. ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-v_HeaeUUOnc.htmlsi=0gqpBHPaduwXHPYh
When handling that a>=b constraint at 16:17, you skipped the implied b!=0 constraint from dividing by b, which results in a t!=0 constraint for the curve overall. That makes sense to me though, because without the t!=0 constraint, it would be implying that unsorted, uniformly-distributed data approaches this curve.
That algorithm is cocktail shaker sort, which is the same as bubble sort, except you bounce back and forth when you get to the end instead of jumping back to the beginning. Both the top curve and the bottom curve are hyperbolas, just like bubble sort's curve, but they are positioned a bit differently.
Very interesting and inspiring video, blog, and draft. However, from the mathematical point of view, there is some discrepancy between what you claimed to prove and what you actually proved. First of all infinities and probabilities are tricky things together, as probability is a measure of its own kind, it needs to be carefully studied so that the events stay in controllable size when approaching infinity. Secondly, as the initial state of the list follows a probability distribution, so does the unsorted section after some iterations. From the probabilistic viewpoint, your curve does not seem to represent anything: If we have numbers from 1 to N to be sorted from their uniform random placements and we know that N-n elements are in their correct places, this is not enough information to conclude scale-invariancy nor continuity over the whole domain. If we think about the expected curve, there will be a discontinuity point at 1-t, because if the element x[(1-t)N] is in the end part of the list at the beginning, it will end up in the correct place, otherwise, the (1-t)N'st element is uniformly any element less than x[(1-t)N], therefore, the expected value is: E(X[(1-t)N]) = 0.5*(x[(1-t)N]-1)*t + x[(1-t)N]*(1-t) = x[(1-t)N] - 0.5*(x[(1-t)N]+1)*t. If I use this to scale the function, it mostly undershoots. As an upper bound, it does not make sense either because distribution P(X[k] <= x[k]) is uniform with a minimum P(X[1] <= x[1]) = t as it will be the first element only if it appears on the unsorted side. From this, I can derive feasible upper and lower bounds by setting either E(X[k] <= x[k])=0 or E(X[k] > x[k]) = 0. The upper bound is always greater than N*x/(x+t) and the lower bound surpasses the curve, so it is not representative of the Bubble-sorting behavior as the height of the bars will be always between these values, see illustration at t=0.4 if Wolfram will not fail me: www.wolframalpha.com/input?i=plot+0.4*1%2B%281-0.4%29*k%2B1%2F2+%281-k%29+%28+k+%2B+1%29*%281-0.4%29%2F1%2C+1.4*k%2F%28k%2B0.4%29%2C+%280.4%2B0.6*k%29%28k%2B1%29%2F2%2C+k%3D0..1 What your proof in the paper and blog presents is that the curve Bubble sort algorithm forms, will approach the function x/(x+t). If someone from a college background reads this, limits are usually taught wrong there. Approaching only means that we go towards something, there is no guarantee to reach the limit calculated with a reasonable amount of steps. It also does not mean that the Bubble sort curve can be approximated by its limit as it does not work as a bound.
It would be interesting to see what stochastic theory would have to say about doing the process in reverse: ie starting with a sorted list, going from left to right and the looping back, randomly swap a pair of adjacent values if they were in order (so that running the process in reverse, the bubble sort algorithm would choose to swap the pair to reorder them). It defines a random walk in the set of permutations of the sorted list, and it could be fun to see what you could get from analysing it (but sadly I only know the very basics).
I haven't looked at your paper, but you can get a rigorous derivation by observing that the position x - t after t sweeps is occupied by the minimum of the original value at position x and the (x - t)-th order statistic of the empirical distribution of the first x elements in the original list. By the law of large numbers, the empirical distribution converges in distribution to uniform as the size of the list increases, and the order statistic is almost surely the quantile function. Then you have f(x - t, t) = (x - t)/x.
