The Bubble Sort Curve 

A few notes which might be of interest, but which didn't fit in the video: - 3:27 - I'm using a loose pseudocode to represent the algorithm as compactly as possible. The for loops go to N - 2, inclusive. For some reason, that felt more natural to me. - Most of the list sorting animations use a more optimized version of the algorithm than what I step through. Since the largest n items are sorted after n iterations, we can stop the scan early, so each iteration is quicker than the last one. I used the slower version for the math because it is simpler to pretend that every iteration takes an equal amount of time. To transform the result into the more optimized version, just replace t with 1 - √(1 - t). - I "cheated" a bit for some of the animations by using specifically designed shuffles to make the curve really clear (0:02, 0:23, 16:54). The curve starts becoming really clear with random shuffles when the size of the list gets into the thousands (like at 2:30). But when the list length is in the low hundreds, it's usually pretty lopsided (like at 1:18). I think the low hundreds size is the most visually pleasing, so I figured that a slightly fudged shuffle was worth the extra visual clarity.

Babe not now, factorial guy just dropped

The most impressive part of it is that you did not skip the rigor, you wrote up a 26 page paper exploring the details. Really cool video.

the curve matching is a lot more satisfying than any sorting video i have seen

You realize you probably have one of the best average video quality on RU-vid, right? 4 videos, all killer, no filler.

17:50 "Which this epilogue is too small to contain", i.e. it will be proven in 350 years with methods not yet available to us. Here's to hoping 🤞. Great video btw!

the way you gray out the inequality and move it to the side, and the way you color and increase or decrease the size of relevant parts of the graphs and equations is SO HELPFUL and i imagine tricky to get exactly right. i really appreciate it

This problem has been stuck in my head for a long time. You don't know how surprised and excited I was when I saw this video explaining the exact problem appears in the recommendation! Thank you so much for making this video.

16:22 I can't even imagine the work you put in that ≥ to ≤ transition in manim. Great video as always.

Bro just comes in every year or so and just drops a banger on us

The assumption part should also address why you are ignoring the dips and only fitting a tarp-like shape. Because the shape is only apparent to a human eye constantly searching for a pattern if you are using bars. If you use a scatter plot to represent the same process, the "shape" a human eye are seeing will actually become a string instrument, an American football-shaped part before x, and a straight line pass x.

This is extremely cool! You’re essentially something called a “permuton”. These have become a hot topic over the last several years, but I haven’t seen anyone look at the “bubble sort permuton”.

I think the intuitive element of why this shape forms will come from the fact in bubble sort all the larger values will tend to drift to the right more rapidly than the smaller values move left. As you say smaller values will only ever move left once per iteration, but any larger values prior to the largest unsorted value will make multiple moves until the next largest value is found. From this, because the shape we are perceiving comes from the larger values in any local area, then you'll always get a shape that rapidly climbs to start, and increases more gradually towards it's end.

You went this far.. for a sorting algorithim? Absolutely insane. It was satisfying as hell watching the curve plotted against sorting.

16:48 for anyone wanting to graph this in desmos, to turn it into a recreation of the optimised bubble sort: - add the equations "y = {0

That final animation of the curve that you found matching the data so smoothly was...jaw-dropping. 😲

YOOO lines that connect is back !!

I have been asking myself this very question every now and then for years, but never took the time to look at it closely. I am so glad you made this video and that I found it. Loved it

I absolutely love mathematics that are complex enough to be interesting yet simple enough to not require a degree to understand if explained in an engaging and informative way. And your excellent use of graphics and animation to demonstrate concepts that would otherwise be difficult to express verbally, that is just /chefskiss.

I love the math videos where its not for academic purposes and is just someone talking about and researching something they love. Just started the video but I know im gonna love it, good job

I saw your presentation about this at a conference, maybe a month ago. I think maybe you said I was the first person you'd met that had seen your videos. This explanation is much clearer. Thank you.

Gorgeous. I always wondered what that curve was approximating, but imagined a proper derivation would be far more complicated than this. You're a smart guy, LTC. Keep it up

You should do a whole video on the Euler-Mascheroni constant, would be really interesting in your style

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.

Your videos are some of few where you can watch them an unlimited amount of time and still learn something new every time. Keep up the great work.

Thank's man. You really made my night. I commit, I couldn't follow everything you said, but seeing the function draw it's graph was absolutely worth my time. Happy that you're back.

All these years I've noticed that curve and wondered if there was a way of fitting it, but I lacked the mathematical fluency to step through the process you did. Nice.

this is just absolutely crazy. Every time you upload a video you keep surprising me with your everlasting increase in quality. The animations were incredibly smooth, at every single frame i had all the information i needed, no more, no less, and distributed THE best way possible. An incredible aesthetic, beautiful colors and design supporting an explanation that was precise and great. Please keep uploading videos of such quality, you are one the best math youtubers that have ever existed, no doubts at all.

Just amazing. Love the “nice” moment. Please keep posting!!! Love your stuff!!!

great video, and really smooth graphics! always interesting to see maths applied to subjects where it isn't necessary

THANK YOU! I have been thinking about this since one of the first times I watched a sorting algorithms video and, as you said, there isn't much information on the internet about this specific problem. This was so cool to watch, you're also a great storyteller.

Been a while! Glad to see you’re back.

I love your videos, so glad to see you're back!

Return of the King

Amazing! Always like to find the limits of discrete processes. Thank you

Finally, I thought for a second that no more videos would accur and yet, boom, here you are! Great to see you back!

This was gorgeous! Initially, I didn't know how you would have tackled the problem. As soon you brought out the similarity condition I had an enlightenment. Beautiful problem, beautiful solution, splendid explanation!

I missed your videos, glad to see you again my guy

I took the challenge to find the curve myself, and my central idea was this: For the bar height Y to end up at position X after T iterations, there need to have been exactly T bars before position X that were higher than Y. For ease of notation, let's instead talk about the normalized values x = X/N, y = Y/N and t = T/N, where N is the size of the array. The factors N would cancel out in the end anyway. The likelihood of there being exactly k bars higher than y before position x is given by a binomial distribution: P(k) = (1-y)^k * y^(x-k) * (x choose k). For larger N, this distribution contracts around its expected value until in the limit N -> infinity, all the probability mass is _at_ the expected value and we are certain that the condition is fulfilled at step t = (1-y) * x. This doesn't quite define the right curve yet, because the original condition neglected that the bars are moved one spot to the left when an iteration passes them. After t iterations, values are shifted a distance t to the left. We represent this by replacing x with (x+t) in the formula: t = (1-y) * (x+t) t = x + t - y * (x+t) y * (x+t) = x y = x / (x+t) There we go. If we want to include the already sorted bit, we can write y = max( x / (x+t), x ).

I just wanted to say that this is amazing. You provided not only an excellent video for RU-vid, but an entire paper with a mathematical proof for anyone interested in the topic. This is what educational RU-vid videos should be. Great work and please keep going, this is how popularizing math and computer science should look like! Also, the whole premise of this topic is so simple, yet so non-trivial to think about. I'm almost angry that I didn't think about this problem myself :)

this is such an interesting application of functional equations, I love how we start with the conditions the functions must satisfy and somehow narrowing it down to one possible solution

I’ve been wondering about this exact question for years. Thank you so much!

This is so amazing question, approach, and answer. Thank you so much

This was genuinely beautiful

Never thought about this before, but the moment I saw the thumbnail I was intrigued!

One little addition to the graph: you picked the scale 1x1 so everything outside 0

Incredible video! I first imagined that some stochastic techniques would be needed, but your parametric approach was simple, comprehensive, and beautiful at once. To generalize the result to non-uniform elements in the array, you can just say that you work with their quantiles.

After all the work to see the curve fit so well... perfection

Really interesting concept to explore, the a-ha moment at 14:23 really did it for me. Awesome stuff!

Whoa. I’m not a maths person but what little I got was beautiful. I feel like I understand why people enjoy maths a bit better.

this s the most satisfying thing i watched in recent days..... we need more videos from you.... amazing stuff.... i have become big fan of your work....

Subscribed. When the music kicks in at 16:54, I got emotional. You do a good job of hinting that this function is recursively defined in nature, which leads to an explicit formula, similar to how some sequences can be solved.

Wonderful! Informative! Well presented, written, and recorded! Please continue doing this, keep up the excellent work

This is absolutely beautiful. For many math videos out there, I could guess where it’s heading just from the thumbnail/title. This one stunned me. I guessed that this might need some differential equations or some sort of series and end up with something like natural log. Turns out just a few weeks of Calculus 1 would do. Gorgeous! Edit: I usually don’t give a like to videos, but you deserved it.

This is the kind of content I love most, even if I don't end up watching them most. Excellent job!

To say this content is as wonderfully illustrated and animated as the content of this one blue, three brown guy (or whatever his nickname is) wouldn't be an exaggeration. The presentation is nothing short of excellently executed and gives a masterclass in teaching. What a joy to join in and getting educated! Thanks a lot for all the enormous effort and time you put into this marvellous piece of edutainment! 😊

Very nice exploration and explanation! Will now immediately check out your prior vids, and, very likely, subscribe. Good stuff!

This video is beautiful. Thank you.

I used to suggest 3b1b for math videos to all my math students, but now I suggest LTC, it's just pure magic to be honest.

Man I have been eagerly waiting on you. Glad to see you back :D

One of the most beautiful videos I’ve watched in a while, this is why I love maths.

One of the best videos about math an programing i have ever seem!

Amazing display of creativity. Congrats and thank you!

What a great question to ask! I could've watched a dozen more examples of the curve perfectly matching a real sorting like 16:54

what an amazing derivation, so simple yet so satisfying

Nice video. The derivation of the closed form was well established and you answered all key question I'd worry about.

I thought you would need to use the fact that a bar stops at the left of the first encounter of a bar that is the taller than itself This is very elegant!

You're one of the clearest math youtubers out here!

Thank you! The first time I've watched some animated sorting algo comparision I asked myself the same question.

This was so satisfying. Amazing!

Have you ever seen those memes that say "pick two: Fast, Cheap, Good" Well, I feel like you identified the equivalent for math proofs. "Pick two: Correct, Intuitive, Rigorous" Well, the choice is really which one to exclude. Excluding 'Correct' is not acceptable in math, or really ever, but the video you have provided combined with the long paper proof you worked out have provided all three to those who want it. It is inspiring how well you have found a clever way to explain this without the headache, and how well you have documented it in its most rigorous form in your blog. Thank you. I hope I can one day do work as good as this.

I literally just checked your channel last week for any new videos and thought "what a shame, looks like there's no more coming", and then you drop a new vid, let's go!

absolutamente increíble!!! muchísima calidad, gracias!!

Wow! This video is less than a day old and has less than 50k views? It seems like the kind of video I'd watch from some giant maths channel that came out several years ago and has amassed millions of views. This has instantly earned my sub

This is absolutely beautiful

Simply beautiful in presentation.

Just absurdly amazing!!!

Bro this is so cool. I am so proud of you

This was honestly beautiful, an incredible example of the mathematical analysis that happens in computer science

Beautiful! Very nice question, well explained throughout

Beautiful. Just beautiful

wonderful video, love how followable the assumptions and process were

Such a beautiful result for such a messy problem!

Nice. When I was watching these visualizations long time ago, I also noticed that it is creating some hyperbola or something, but never digged dipper. Interesting way of using scaling law to figure out the formula. It is still a bit mysterious why it actually works, but I guess, random something something makes it so. Will read your blog too, because it still bugs me up. Really good video.

I've always noticed this, nice to see a video on it!

One of the GOATS is back

Wow, this videos has such high production quality!

Awesome video man! You'll never let me down!

I think it's super interesting that, if I understand correctly, you never encoded a directive into your proof that the curve should follow the *peaks*, or like, a convex hull or something, of the bubble sort. You were just like, "let there be a continuous curve that behaves nicely and connects up to the diagonal bit"... and the maths decided to give you back a curve that very specifically follows the peaks/convex hull of the bubble sort... am I missing something, or is that kinda weird?

Beautiful derivation! Keep up the great work :)

that was a perfect way to end the day on thank you.

This style is fantastic. I’m a community college dropout and I understood this entire video while stoned out of my body. Absolutely impressive work!!

Absolutely HEAVENLY. What an immaculate video.

Holy hell you’re back!

I would love to see an extention to this video... I absolutely loved bubble sort and wanted to know more about that curve (others did also).... this video of yours provides that information really well (and probably the 1st of any).. thank you

The line fitting was essentially the climax of this video after all the edging, while the algebraic dance was the final most intense act

Exactly!! I've been wondering about this for the longest time as well. Count me impressed! :)

Fantastic. I loved it so much.

simply amazing

I figured it out intuitively at about 7 minutes into the video; I realised by sorting from right to left, it is equivelant to simply removing the bars from tallest to shortest while also shifting the shorter ones leftward. That would make a triangle - HOWEVER because you put those tallest bars at the end and 'scrunch up' the gaps they leave, it sort of squishes the triangle leftwards, creating the curve. This is because the larger bars are pushed rightwards every iteration it skews the triangle into the curve.