{
  "wireMagic": "pb3",
  "pens": [ {
  
  } ],
  "wsWinStyles": [ {
  
  } ],
  "wpWinPositions": [ {
  
  } ],
  "events": [ {
    "tStartMs": 0,
    "dDurationMs": 4600,
    "segs": [ {
      "utf8": "A few years ago, a computing \nlecturer accidentally discovered  "
    } ]
  }, {
    "tStartMs": 4600,
    "dDurationMs": 5560,
    "segs": [ {
      "utf8": "a sorting algorithm in that they were lecturing \nand they're like, \"Oh, here's an example of some  "
    } ]
  }, {
    "tStartMs": 10160,
    "dDurationMs": 5120,
    "segs": [ {
      "utf8": "pseudo code that doesn't sort.\" And I don't know \nhow they found out, maybe a student was like, \"Uh  "
    } ]
  }, {
    "tStartMs": 16040,
    "dDurationMs": 6320,
    "segs": [ {
      "utf8": "uh that works.\" And it did. It actually worked \nas a sorting algorithm, not just sort of just  "
    } ]
  }, {
    "tStartMs": 22360,
    "dDurationMs": 7160,
    "segs": [ {
      "utf8": "sort. I mean, it turns out code, just like \neverything evolves to become a crab, all code  "
    } ]
  }, {
    "tStartMs": 29520,
    "dDurationMs": 9024,
    "segs": [ {
      "utf8": "becomes a sorting algorithm. And uh we're going to \nwe're going to have a closer look at it. [music]"
    } ]
  }, {
    "tStartMs": 38544,
    "dDurationMs": 4096,
    "segs": [ {
      "utf8": "[music]  "
    } ]
  }, {
    "tStartMs": 42640,
    "dDurationMs": 4520,
    "segs": [ {
      "utf8": "First things first, as is the theme today, what \nis a sorting algorithm? Well, here I have some  "
    } ]
  }, {
    "tStartMs": 47160,
    "dDurationMs": 4800,
    "segs": [ {
      "utf8": "squares in the wrong order. I always want these to \ngo from smallest to biggest, your left to right.  "
    } ]
  }, {
    "tStartMs": 51960,
    "dDurationMs": 4040,
    "segs": [ {
      "utf8": "And as a human, I'd be like, \"Well, there's the \nsmallest one, so I'm going to pull that one out,  "
    } ]
  }, {
    "tStartMs": 56000,
    "dDurationMs": 4800,
    "segs": [ {
      "utf8": "swap it with the one which is where it should be.\" \nAnd then I'll look and go, \"Uh there's the next  "
    } ]
  }, {
    "tStartMs": 60800,
    "dDurationMs": 5120,
    "segs": [ {
      "utf8": "smallest.\" And what I'm doing, cuz I'm always \nselecting the next one that needs to be moved  "
    } ]
  }, {
    "tStartMs": 65920,
    "dDurationMs": 5840,
    "segs": [ {
      "utf8": "up the list, this is just called selection sort. \nAnd what I'm doing here, ah done. What I'm doing  "
    } ]
  }, {
    "tStartMs": 71760,
    "dDurationMs": 4520,
    "segs": [ {
      "utf8": "here is just finding, each time I scan the whole \nlist, find the next one that's in the wrong place,  "
    } ]
  }, {
    "tStartMs": 76280,
    "dDurationMs": 5040,
    "segs": [ {
      "utf8": "move it up to where it should be. And that kind \nof gives us the two different aspects to sorting  "
    } ]
  }, {
    "tStartMs": 81320,
    "dDurationMs": 5320,
    "segs": [ {
      "utf8": "algorithms. There's the actual logic behind what \nyou're doing, and then separately, and some would  "
    } ]
  }, {
    "tStartMs": 86640,
    "dDurationMs": 5920,
    "segs": [ {
      "utf8": "say more importantly, how would you code that up \nso a computer can do it automatically. Fun fact,  "
    } ]
  }, {
    "tStartMs": 92560,
    "dDurationMs": 6840,
    "segs": [ {
      "utf8": "I made these opening titles that you saw a moment \nago using selection sort. I scrambled it into 120  "
    } ]
  }, {
    "tStartMs": 99400,
    "dDurationMs": 4120,
    "segs": [ {
      "utf8": "vertical strips and then sorted them back into \norder. It's a nice way to visualize it. So,  "
    } ]
  }, {
    "tStartMs": 103520,
    "dDurationMs": 6440,
    "segs": [ {
      "utf8": "here are four more. Now, these aren't all the \nsame speed. I've had to speed up cocktail shaker  "
    } ]
  }, {
    "tStartMs": 109960,
    "dDurationMs": 4080,
    "segs": [ {
      "utf8": "and insertion so that it's done in the time \navailable, whereas quick sort, look at that,  "
    } ]
  }, {
    "tStartMs": 114040,
    "dDurationMs": 5160,
    "segs": [ {
      "utf8": "it's actually done. It's just that quick. And \nmerge sort, oh my goodness, love merge sort.  "
    } ]
  }, {
    "tStartMs": 119200,
    "dDurationMs": 5440,
    "segs": [ {
      "utf8": "That's also going at the same steady pace. But I \nwant to speed it up because you can see kind of  "
    } ]
  }, {
    "tStartMs": 124640,
    "dDurationMs": 6560,
    "segs": [ {
      "utf8": "like how it's working. Look, it's making low-res \nversions of me and then merging them all together.  "
    } ]
  }, {
    "tStartMs": 131200,
    "dDurationMs": 6520,
    "segs": [ {
      "utf8": "Ah, it's great. We'll get to some actual sorting \nalgorithms in a moment, ridiculous and otherwise.  "
    } ]
  }, {
    "tStartMs": 137720,
    "dDurationMs": 3560,
    "segs": [ {
      "utf8": "But you might be thinking, why do I have to care \nabout sorting algorithms? Like computers do that  "
    } ]
  }, {
    "tStartMs": 141280,
    "dDurationMs": 6080,
    "segs": [ {
      "utf8": "for me. And that's one of the reasons. Computers \nhave got a sort. Like the moment you start writing  "
    } ]
  }, {
    "tStartMs": 147360,
    "dDurationMs": 4680,
    "segs": [ {
      "utf8": "code, you're going to need a sorting algorithm, \nbe it like for data processing or even like like  "
    } ]
  }, {
    "tStartMs": 152040,
    "dDurationMs": 6240,
    "segs": [ {
      "utf8": "now. If you want to sort the comments under this \nvideo by most recent because you're some kind of  "
    } ]
  }, {
    "tStartMs": 158280,
    "dDurationMs": 4280,
    "segs": [ {
      "utf8": "monster. You can do that and there's some \ncode in the background running a sorting  "
    } ]
  }, {
    "tStartMs": 162560,
    "dDurationMs": 3440,
    "segs": [ {
      "utf8": "algorithm. So it's an unavoidable part of \nwriting code. But you think, well, hang on,  "
    } ]
  }, {
    "tStartMs": 166000,
    "dDurationMs": 6600,
    "segs": [ {
      "utf8": "it's already been solved. I just import sort \nthing. Well, thinking through the logic of how  "
    } ]
  }, {
    "tStartMs": 172600,
    "dDurationMs": 7480,
    "segs": [ {
      "utf8": "a sorting algorithm works is a really nice way to \njust teach your brain how to understand, follow,  "
    } ]
  }, {
    "tStartMs": 180080,
    "dDurationMs": 4800,
    "segs": [ {
      "utf8": "and use algorithms. So in terms of a learning \ntool, highly recommend it. Probably be why there  "
    } ]
  }, {
    "tStartMs": 184880,
    "dDurationMs": 4360,
    "segs": [ {
      "utf8": "was a lecture on it which caused this whole thing \nto start. And job interviews, like if you want  "
    } ]
  }, {
    "tStartMs": 189240,
    "dDurationMs": 5320,
    "segs": [ {
      "utf8": "to become a software developer, this is a classic \nquestion to have to write out some pseudo code for  "
    } ]
  }, {
    "tStartMs": 194560,
    "dDurationMs": 6000,
    "segs": [ {
      "utf8": "different sorting algorithms. And finally, it's \nfun. I like it. Recreational sorting algorithms,  "
    } ]
  }, {
    "tStartMs": 200560,
    "dDurationMs": 5120,
    "segs": [ {
      "utf8": "I think I think they're great. So I'm on board. \nSo there's my four reasons. And at the moment  "
    } ]
  }, {
    "tStartMs": 205680,
    "dDurationMs": 5640,
    "segs": [ {
      "utf8": "in the wrong order, so I'll just sort them into \norder I care about. There you are. They're fun.  "
    } ]
  }, {
    "tStartMs": 211880,
    "dDurationMs": 4440,
    "segs": [ {
      "utf8": "And I don't want I don't want to risk getting a \njob. Okay, the first algorithm we're going to look  "
    } ]
  }, {
    "tStartMs": 216320,
    "dDurationMs": 6520,
    "segs": [ {
      "utf8": "at is a classic of the genre, bubble sort. This \nis the sorting algorithm that it seems everybody  "
    } ]
  }, {
    "tStartMs": 222840,
    "dDurationMs": 6120,
    "segs": [ {
      "utf8": "knows, but also everybody hates. What is the most \nefficient way to sort a million 32-bit integers?"
    } ]
  }, {
    "tStartMs": 232680,
    "dDurationMs": 5720,
    "segs": [ {
      "utf8": "Well, uh I'm I'm maybe I'm I'm sorry. Maybe \nwe should No, no, no, no, no. I I I think  "
    } ]
  }, {
    "tStartMs": 238400,
    "dDurationMs": 4360,
    "segs": [ {
      "utf8": "I I I think I think the the bubble sort would \nbe the wrong way to go. But before we get to the  "
    } ]
  }, {
    "tStartMs": 242760,
    "dDurationMs": 4800,
    "segs": [ {
      "utf8": "exact details of stepping through bubble sort, \nit occurs to me some of you may want a job.  "
    } ]
  }, {
    "tStartMs": 248240,
    "dDurationMs": 5680,
    "segs": [ {
      "utf8": "I mean, as a software developer or turns out \npresident. And in that case, you're going to  "
    } ]
  }, {
    "tStartMs": 253920,
    "dDurationMs": 6440,
    "segs": [ {
      "utf8": "love the sponsor of today's video, boot.dev. It is \na fantastic, interactive, and indeed addictive way  "
    } ]
  }, {
    "tStartMs": 260360,
    "dDurationMs": 5080,
    "segs": [ {
      "utf8": "to learn modern software developer skills. \nI mean, we're talking Python, SQL, Go,  "
    } ]
  }, {
    "tStartMs": 266240,
    "dDurationMs": 5720,
    "segs": [ {
      "utf8": "other languages. Check out all these courses I \ncan do. I'm so excited. Now, a bunch of you are  "
    } ]
  }, {
    "tStartMs": 271960,
    "dDurationMs": 6080,
    "segs": [ {
      "utf8": "thinking, \"Obviously, Matt, you're a terrible \nPython coder. You're going to learn Python for  "
    } ]
  }, {
    "tStartMs": 278040,
    "dDurationMs": 5320,
    "segs": [ {
      "utf8": "beginners. Come on, get in there.\" But no, you'd \nbe wrong. Going to go back. I'm going to learn  "
    } ]
  }, {
    "tStartMs": 283360,
    "dDurationMs": 5800,
    "segs": [ {
      "utf8": "Git. Oh, look, the name is the primogen. Huh. \nRight, so here we go. I'm going to do this, and  "
    } ]
  }, {
    "tStartMs": 289160,
    "dDurationMs": 7480,
    "segs": [ {
      "utf8": "you'll never be able to mock my version control \nagain. All the content on boot.dev is free for you  "
    } ]
  }, {
    "tStartMs": 296640,
    "dDurationMs": 5560,
    "segs": [ {
      "utf8": "to read and watch. So, you've got no excuses. \nAnd if you do get a paid membership, 25% off  "
    } ]
  }, {
    "tStartMs": 302200,
    "dDurationMs": 5520,
    "segs": [ {
      "utf8": "if you use my code, that means you access all the \ninteractive elements. We've got hands-on coding,  "
    } ]
  }, {
    "tStartMs": 307720,
    "dDurationMs": 5760,
    "segs": [ {
      "utf8": "AI assistance, progress tracking, and game \nmechanics. That's a good deal. So, if you  "
    } ]
  }, {
    "tStartMs": 313480,
    "dDurationMs": 6280,
    "segs": [ {
      "utf8": "want to learn to code or just improve your skills, \njoin me at boot.dev. Discount code standupmaths.  "
    } ]
  }, {
    "tStartMs": 319760,
    "dDurationMs": 4560,
    "segs": [ {
      "utf8": "Come on this adventure together. Thanks to \nboot.dev for sponsoring this video. And if  "
    } ]
  }, {
    "tStartMs": 324320,
    "dDurationMs": 6160,
    "segs": [ {
      "utf8": "you use the QR code on screen right now or the \nlink in the description, you can get 25% off  "
    } ]
  }, {
    "tStartMs": 330480,
    "dDurationMs": 5320,
    "segs": [ {
      "utf8": "your first annual membership. Learn coding. \nLearn how to do things like putting ridiculous  "
    } ]
  }, {
    "tStartMs": 335800,
    "dDurationMs": 6920,
    "segs": [ {
      "utf8": "pi symbols in QR codes automatically. Uh on which \nI have no further comment. Thanks, boot.dev. Now,  "
    } ]
  }, {
    "tStartMs": 343360,
    "dDurationMs": 7120,
    "segs": [ {
      "utf8": "I think these are probably randomized enough. \nLet's talk bubble sort. To do our bubble sort,  "
    } ]
  }, {
    "tStartMs": 350480,
    "dDurationMs": 5800,
    "segs": [ {
      "utf8": "we're going to start with a counter I over here \nat index zero. So, because this is computing,  "
    } ]
  }, {
    "tStartMs": 356280,
    "dDurationMs": 8800,
    "segs": [ {
      "utf8": "we're going to go position zero, 1 2 3 4, and all \nwe do is look at position I compared to I + 1,  "
    } ]
  }, {
    "tStartMs": 365080,
    "dDurationMs": 4760,
    "segs": [ {
      "utf8": "and if they're in the wrong order, we swap \nthem. If they're not, we don't. And so,  "
    } ]
  }, {
    "tStartMs": 369840,
    "dDurationMs": 4440,
    "segs": [ {
      "utf8": "the first two are in the wrong order, so I swap \nthose. Here we are, cuz now it goes smaller  "
    } ]
  }, {
    "tStartMs": 374840,
    "dDurationMs": 4840,
    "segs": [ {
      "utf8": "bigger. Then we compare the next two. They're \nin the wrong order, so we swap them. Smaller  "
    } ]
  }, {
    "tStartMs": 379680,
    "dDurationMs": 4680,
    "segs": [ {
      "utf8": "bigger. And you may notice, because this is \nlike the second biggest and a smaller bigger,  "
    } ]
  }, {
    "tStartMs": 384360,
    "dDurationMs": 5600,
    "segs": [ {
      "utf8": "it's going to bubble all the way up until it \ngets here. Now, these are in the right order,  "
    } ]
  }, {
    "tStartMs": 389960,
    "dDurationMs": 4280,
    "segs": [ {
      "utf8": "so we go back to the beginning again. Next pass, \nthe first two are already in the right order.  "
    } ]
  }, {
    "tStartMs": 394240,
    "dDurationMs": 5240,
    "segs": [ {
      "utf8": "The next two are in the wrong order, so we swap \nthose, and then everything else is correct,  "
    } ]
  }, {
    "tStartMs": 399480,
    "dDurationMs": 4120,
    "segs": [ {
      "utf8": "and then we go back over. They're in the wrong \norder, so we swap them, and everything else  "
    } ]
  }, {
    "tStartMs": 403600,
    "dDurationMs": 5680,
    "segs": [ {
      "utf8": "is correct. And as soon as we can do a complete \npass comparing every pair and they're all right,  "
    } ]
  }, {
    "tStartMs": 409280,
    "dDurationMs": 5080,
    "segs": [ {
      "utf8": "we know we are finished. That is bubble sort. \nThat felt like fun. It didn't take that long.  "
    } ]
  }, {
    "tStartMs": 414360,
    "dDurationMs": 5920,
    "segs": [ {
      "utf8": "So, you know what? Let's Let's see if we can \nput it together in some pseudo code. N minus  "
    } ]
  }, {
    "tStartMs": 421280,
    "dDurationMs": 5280,
    "segs": [ {
      "utf8": "two. Okay, so I've done for I equals zero, which \nmeans it starts there in the zeroth position,  "
    } ]
  }, {
    "tStartMs": 426560,
    "dDurationMs": 4840,
    "segs": [ {
      "utf8": "to N minus two. This will be the N minus one \nposition, that's the N minus two position.  "
    } ]
  }, {
    "tStartMs": 431400,
    "dDurationMs": 10080,
    "segs": [ {
      "utf8": "We want to stop one short, because then \nwe take uh if I is greater than I + 1."
    } ]
  }, {
    "tStartMs": 444080,
    "dDurationMs": 6240,
    "segs": [ {
      "utf8": "Because here, we always compare I \nto I + 1, so I has to stop here,  "
    } ]
  }, {
    "tStartMs": 450320,
    "dDurationMs": 4920,
    "segs": [ {
      "utf8": "so we have an I + 1 to compare it to. That's \nthe final pair. And if I is greater than I + 1,  "
    } ]
  }, {
    "tStartMs": 455240,
    "dDurationMs": 3760,
    "segs": [ {
      "utf8": "which means they're the wrong way around, \ncuz we want them smaller to bigger,  "
    } ]
  }, {
    "tStartMs": 459000,
    "dDurationMs": 5560,
    "segs": [ {
      "utf8": "I'm just saying here, take the list position \nI and list position I plus one and swap them.  "
    } ]
  }, {
    "tStartMs": 464560,
    "dDurationMs": 6040,
    "segs": [ {
      "utf8": "So, that becomes equal to that and that becomes \nequal to that. Although, oh wait, we need to stop  "
    } ]
  }, {
    "tStartMs": 471240,
    "dDurationMs": 4480,
    "segs": [ {
      "utf8": "once we do a complete pass and nothing \nchanges. So, what you'll probably do"
    } ]
  }, {
    "tStartMs": 477960,
    "dDurationMs": 4040,
    "segs": [ {
      "utf8": "All right, this is not great, but I've put a \nbit of extra room at the beginning there. So,  "
    } ]
  }, {
    "tStartMs": 482000,
    "dDurationMs": 6160,
    "segs": [ {
      "utf8": "each time it goes through iterates through this, \nit resets finished to true, but then if it has to  "
    } ]
  }, {
    "tStartMs": 488160,
    "dDurationMs": 6600,
    "segs": [ {
      "utf8": "do a swap, it changes finished to false. And if \nit happens to get through all of these without a  "
    } ]
  }, {
    "tStartMs": 494760,
    "dDurationMs": 6760,
    "segs": [ {
      "utf8": "single flipping to false, it'll hit the end and if \nfinished, so if it's true, it'll return the list.  "
    } ]
  }, {
    "tStartMs": 501520,
    "dDurationMs": 4640,
    "segs": [ {
      "utf8": "But if finished is false, it'll go back up again. \nSo, this way it'll iterate through this over and  "
    } ]
  }, {
    "tStartMs": 506160,
    "dDurationMs": 6600,
    "segs": [ {
      "utf8": "over and over again until one time it doesn't do \nany swaps, finished stays true, and it ends. So,  "
    } ]
  }, {
    "tStartMs": 512760,
    "dDurationMs": 6000,
    "segs": [ {
      "utf8": "there you are. Uh terrible pseudo code for bubble \nsort. And if you are thinking, well, you know  "
    } ]
  }, {
    "tStartMs": 518760,
    "dDurationMs": 5960,
    "segs": [ {
      "utf8": "what? It's not that bad, pretty simple code, very \nstraightforward algorithm. We sorted these pretty  "
    } ]
  }, {
    "tStartMs": 524720,
    "dDurationMs": 7760,
    "segs": [ {
      "utf8": "quickly. It's very inefficient for bigger and \nbigger lists of data because you have to go you  "
    } ]
  }, {
    "tStartMs": 532480,
    "dDurationMs": 5160,
    "segs": [ {
      "utf8": "have to scan like if you've got to move one from \none end to the other end, you have to scan the  "
    } ]
  }, {
    "tStartMs": 537640,
    "dDurationMs": 8720,
    "segs": [ {
      "utf8": "entire list that many times. And so, while it's \nlovely as an example, in practice, it is awful.  "
    } ]
  }, {
    "tStartMs": 547600,
    "dDurationMs": 7840,
    "segs": [ {
      "utf8": "Thanks, Obama. Okay, let me show you what \nthe lecturer, uh someone named Stanley Fung,  "
    } ]
  }, {
    "tStartMs": 555440,
    "dDurationMs": 5200,
    "segs": [ {
      "utf8": "actually did when they were trying to set \nup some pseudo code that would not sort."
    } ]
  }, {
    "tStartMs": 564800,
    "dDurationMs": 6880,
    "segs": [ {
      "utf8": "All right, there it is. That's the entirety of the \npseudo code that Stanley wrote up on the board.  "
    } ]
  }, {
    "tStartMs": 571680,
    "dDurationMs": 5320,
    "segs": [ {
      "utf8": "And they were just making up something that wasn't \ngoing to work. And look how ridiculous this is.  "
    } ]
  }, {
    "tStartMs": 577000,
    "dDurationMs": 5400,
    "segs": [ {
      "utf8": "For equals zero to n minus one, so the the \nfirst counter just points at every single  "
    } ]
  }, {
    "tStartMs": 582400,
    "dDurationMs": 5680,
    "segs": [ {
      "utf8": "item in the list in order. And for each \nof those, J then points at every single  "
    } ]
  }, {
    "tStartMs": 588080,
    "dDurationMs": 5440,
    "segs": [ {
      "utf8": "item in the list in order. And then to cap it \nall off, as well as the ridiculous iteration,  "
    } ]
  }, {
    "tStartMs": 593520,
    "dDurationMs": 5600,
    "segs": [ {
      "utf8": "we always check if if this is correct. So we \nwant I to be smaller than J. If they're right,  "
    } ]
  }, {
    "tStartMs": 599120,
    "dDurationMs": 6320,
    "segs": [ {
      "utf8": "break it. So only if they're in the correct order \nalready, you swap them the other way around.  "
    } ]
  }, {
    "tStartMs": 605440,
    "dDurationMs": 7400,
    "segs": [ {
      "utf8": "And if they're in the wrong order, you leave them \nalone. And it works. Uh spoiler, um it's because  "
    } ]
  }, {
    "tStartMs": 612840,
    "dDurationMs": 6440,
    "segs": [ {
      "utf8": "this ridiculousness accidentally cancels with this \nridiculousness because I and J swap sides. But you  "
    } ]
  }, {
    "tStartMs": 619280,
    "dDurationMs": 4360,
    "segs": [ {
      "utf8": "know what we're going to do? Well, actually we'll \nstep through this and you can see it for yourself.  "
    } ]
  }, {
    "tStartMs": 625640,
    "dDurationMs": 5320,
    "segs": [ {
      "utf8": "Okay, here we go. This is so stupid, I love \nit. So uh first counter I starts over here at  "
    } ]
  }, {
    "tStartMs": 630960,
    "dDurationMs": 6480,
    "segs": [ {
      "utf8": "position zero. J also zero. We compare this to \nitself because there are no efficiencies here  "
    } ]
  }, {
    "tStartMs": 637440,
    "dDurationMs": 5320,
    "segs": [ {
      "utf8": "and uh it's not smaller than itself, so it gets \nto stay. Okay, next step. We now compare this to  "
    } ]
  }, {
    "tStartMs": 642760,
    "dDurationMs": 4640,
    "segs": [ {
      "utf8": "all of them. So we compare it to this one. They're \nin the wrong order. They're descending, which is  "
    } ]
  }, {
    "tStartMs": 647400,
    "dDurationMs": 5720,
    "segs": [ {
      "utf8": "incorrect, so we leave them. We compare these two. \nOh, they're the right order. Okay, let's fix that.  "
    } ]
  }, {
    "tStartMs": 653120,
    "dDurationMs": 6240,
    "segs": [ {
      "utf8": "Please. There we go. Now we continue to compare \nthis position. So uh they're in the wrong order,  "
    } ]
  }, {
    "tStartMs": 659360,
    "dDurationMs": 4240,
    "segs": [ {
      "utf8": "they're in the wrong order. First pass complete \nand you may have noticed what it's done  "
    } ]
  }, {
    "tStartMs": 663600,
    "dDurationMs": 4920,
    "segs": [ {
      "utf8": "is it's taken the biggest item and moved it to \nthe zeroth position, the beginning of the list,  "
    } ]
  }, {
    "tStartMs": 668520,
    "dDurationMs": 4800,
    "segs": [ {
      "utf8": "and it will always do that. So remember that. \nOkay, second pass. Now you're going to watch  "
    } ]
  }, {
    "tStartMs": 673320,
    "dDurationMs": 5960,
    "segs": [ {
      "utf8": "this real close because this is now position I, \nbut J still starts at the beginning. And actually  "
    } ]
  }, {
    "tStartMs": 679280,
    "dDurationMs": 5720,
    "segs": [ {
      "utf8": "we're looking at them from the other side now \nbecause J is before I. So when we compare these,  "
    } ]
  }, {
    "tStartMs": 685600,
    "dDurationMs": 4160,
    "segs": [ {
      "utf8": "we're actually comparing them in the reverse \ndirection and they are in the right order from  "
    } ]
  }, {
    "tStartMs": 689760,
    "dDurationMs": 6920,
    "segs": [ {
      "utf8": "the wrong direction, so we swap them. And so, \nthese two swap. Now, we compare that to itself.  "
    } ]
  }, {
    "tStartMs": 697200,
    "dDurationMs": 5240,
    "segs": [ {
      "utf8": "All good. And we carry on kind of like before. \nThese are in the wrong order, so they stay.  "
    } ]
  }, {
    "tStartMs": 702440,
    "dDurationMs": 7720,
    "segs": [ {
      "utf8": "Wrong order, they stay. Wrong order, they stay. \nOkay, next pass. I is now here. We're looking  "
    } ]
  }, {
    "tStartMs": 710160,
    "dDurationMs": 6320,
    "segs": [ {
      "utf8": "the wrong way, and they are in the wrong order, \nso they stay. They're in They're in the right  "
    } ]
  }, {
    "tStartMs": 716480,
    "dDurationMs": 7160,
    "segs": [ {
      "utf8": "order from the wrong direction, so they swap. \nYes, okay, I got this. That stays where it is.  "
    } ]
  }, {
    "tStartMs": 724280,
    "dDurationMs": 4440,
    "segs": [ {
      "utf8": "These are in the wrong order, so they \nstay. Wrong order, so they stay. [sighs]  "
    } ]
  }, {
    "tStartMs": 730000,
    "dDurationMs": 6280,
    "segs": [ {
      "utf8": "Two to go. So, we're here. This is our I. J starts \nway over there again. So, we're looking in the  "
    } ]
  }, {
    "tStartMs": 736280,
    "dDurationMs": 6360,
    "segs": [ {
      "utf8": "wrong order, but they're in the wrong order, so \nthey Oh, they stay. That's the correct order, but  "
    } ]
  }, {
    "tStartMs": 742640,
    "dDurationMs": 6040,
    "segs": [ {
      "utf8": "the wrong way around, so they have to swap. Now, \nwe're looking at these. And they have to swap.  "
    } ]
  }, {
    "tStartMs": 749400,
    "dDurationMs": 5000,
    "segs": [ {
      "utf8": "That compared to itself, and then these are in \nthe wrong order, so they stay. Oh, last. How is  "
    } ]
  }, {
    "tStartMs": 754400,
    "dDurationMs": 5880,
    "segs": [ {
      "utf8": "this going to work? Last pass. This one compared \nto the very beginning one are in the wrong order,  "
    } ]
  }, {
    "tStartMs": 760280,
    "dDurationMs": 6000,
    "segs": [ {
      "utf8": "so they stay. Oh, that's why it works. Wrong \norder, so they stay. The correct order from  "
    } ]
  }, {
    "tStartMs": 766280,
    "dDurationMs": 8160,
    "segs": [ {
      "utf8": "the wrong way around, so they swap. And then we \ncompare this. They're in the the wrong direction,  "
    } ]
  }, {
    "tStartMs": 774440,
    "dDurationMs": 5040,
    "segs": [ {
      "utf8": "the wrong, but that cancels, and so they swap. \nAnd then we compare that to itself, and it did it.  "
    } ]
  }, {
    "tStartMs": 780720,
    "dDurationMs": 6040,
    "segs": [ {
      "utf8": "Oh, I can't believe it works. I can't \nbelieve it sorts. God, I love it so much.  "
    } ]
  }, {
    "tStartMs": 787960,
    "dDurationMs": 6760,
    "segs": [ {
      "utf8": "That makes me so angry. That's art. Okay, we all \njust took a moment here to collect ourselves,  "
    } ]
  }, {
    "tStartMs": 794720,
    "dDurationMs": 5720,
    "segs": [ {
      "utf8": "and we're okay now. It's so ridiculous, but you \nmay have noticed how it works. So, it always takes  "
    } ]
  }, {
    "tStartMs": 800440,
    "dDurationMs": 5520,
    "segs": [ {
      "utf8": "the biggest one, chucks it to the wrong end, \nand then drags it all the way up, uh kind of  "
    } ]
  }, {
    "tStartMs": 805960,
    "dDurationMs": 6640,
    "segs": [ {
      "utf8": "plowing through the list. And behind it, it leaves \nthings in the correct order. And that's because  "
    } ]
  }, {
    "tStartMs": 813440,
    "dDurationMs": 6560,
    "segs": [ {
      "utf8": "on the actual business side of the sort, behind \nthe biggest one, J's always on the other side.  "
    } ]
  }, {
    "tStartMs": 820000,
    "dDurationMs": 4800,
    "segs": [ {
      "utf8": "And so, because of they're flipped, doing \nit the wrong way is doing it the right way,  "
    } ]
  }, {
    "tStartMs": 824800,
    "dDurationMs": 4640,
    "segs": [ {
      "utf8": "and they all end up perfectly in order. Although, \na fun side effect, if you start with the list  "
    } ]
  }, {
    "tStartMs": 829440,
    "dDurationMs": 5920,
    "segs": [ {
      "utf8": "already sorted, which things like bubble sort \nwould just leave alone and be like, \"Yep, done.\"  "
    } ]
  }, {
    "tStartMs": 835960,
    "dDurationMs": 5960,
    "segs": [ {
      "utf8": "I can't believe it can sort will always take the \nbiggest one, put it there, and drag it up. So,  "
    } ]
  }, {
    "tStartMs": 841920,
    "dDurationMs": 6520,
    "segs": [ {
      "utf8": "you've got to go through the whole process every \ntime, even if it starts sorted. In that regard,  "
    } ]
  }, {
    "tStartMs": 848440,
    "dDurationMs": 5000,
    "segs": [ {
      "utf8": "a terrible algorithm. But, the reason I think it's \na great algorithm is because it is so surprising,  "
    } ]
  }, {
    "tStartMs": 853440,
    "dDurationMs": 5440,
    "segs": [ {
      "utf8": "and you've really got to think it through. In that \nregard, excellent example for teaching algorithmic  "
    } ]
  }, {
    "tStartMs": 858880,
    "dDurationMs": 5920,
    "segs": [ {
      "utf8": "thinking, which is why, when Stanley Fong stumbled \nacross this trying to come up with the algorithm  "
    } ]
  }, {
    "tStartMs": 864800,
    "dDurationMs": 5600,
    "segs": [ {
      "utf8": "that didn't sort, they wrote a whole paper about \nit. They named it I Can't Believe It Can Sort.  "
    } ]
  }, {
    "tStartMs": 870400,
    "dDurationMs": 3520,
    "segs": [ {
      "utf8": "And it's a great paper. I'll link to it below \nif you want to go check it out. Stanley proves  "
    } ]
  }, {
    "tStartMs": 873920,
    "dDurationMs": 4600,
    "segs": [ {
      "utf8": "why this works. Although, when they're proof, \nthey use index one, so just bear that in mind  "
    } ]
  }, {
    "tStartMs": 878520,
    "dDurationMs": 5200,
    "segs": [ {
      "utf8": "when you see the proof. Lovely paper. I actually \ncontacted Stanley at the time, back in 2021, had  "
    } ]
  }, {
    "tStartMs": 883720,
    "dDurationMs": 6080,
    "segs": [ {
      "utf8": "a chat about it. And Stanley did point out some \npeople were taking the paper a little seriously,  "
    } ]
  }, {
    "tStartMs": 889800,
    "dDurationMs": 4280,
    "segs": [ {
      "utf8": "and they have a whole addendum where they're \nanswering some of the common questions and  "
    } ]
  }, {
    "tStartMs": 894080,
    "dDurationMs": 5760,
    "segs": [ {
      "utf8": "comments and critiques, because Stanley's not \nclaiming no one else ever did this before them.  "
    } ]
  }, {
    "tStartMs": 899840,
    "dDurationMs": 5680,
    "segs": [ {
      "utf8": "They just are the first person who documented it \nand realized how counterintuitive it is. And I'm  "
    } ]
  }, {
    "tStartMs": 905520,
    "dDurationMs": 6200,
    "segs": [ {
      "utf8": "glad they did it. And you know, I'm prepared to \ndeclare that I Can't Believe It Can Sort is my  "
    } ]
  }, {
    "tStartMs": 911720,
    "dDurationMs": 5600,
    "segs": [ {
      "utf8": "official favorite sorting algorithm. Just over 10 \nyears ago, there was this incredible video that  "
    } ]
  }, {
    "tStartMs": 917320,
    "dDurationMs": 7280,
    "segs": [ {
      "utf8": "did an incredible sonification and visualization \nof 15 different sorting algorithms in 6 minutes.  "
    } ]
  }, {
    "tStartMs": 924600,
    "dDurationMs": 5880,
    "segs": [ {
      "utf8": "I'll link to it below if you want to check it \nout. You should. Oh, this This is bubble sort. So,  "
    } ]
  }, {
    "tStartMs": 930480,
    "dDurationMs": 4800,
    "segs": [ {
      "utf8": "you really get a sense cuz you can see which ones \nare being compared and how it's being processed  "
    } ]
  }, {
    "tStartMs": 935280,
    "dDurationMs": 6920,
    "segs": [ {
      "utf8": "how the sorting algorithm actually works. \nAh, that's This really nice. And here we go."
    } ]
  }, {
    "tStartMs": 945560,
    "dDurationMs": 5200,
    "segs": [ {
      "utf8": "Sorted. Now, I'm not going to try and \nrecreate their fantastic sonification,  "
    } ]
  }, {
    "tStartMs": 950760,
    "dDurationMs": 3480,
    "segs": [ {
      "utf8": "but I thought I would take a \nvery large list of random numbers  "
    } ]
  }, {
    "tStartMs": 954240,
    "dDurationMs": 6160,
    "segs": [ {
      "utf8": "and I'd do the equivalent visualization for \nI can't believe it can sort. Here you go."
    } ]
  }, {
    "tStartMs": 964400,
    "dDurationMs": 7720,
    "segs": [ {
      "utf8": "Turns out that Past Mat is a liar. I realized that \nTimo Bingmann, who made that video back in 2013,  "
    } ]
  }, {
    "tStartMs": 972120,
    "dDurationMs": 4840,
    "segs": [ {
      "utf8": "put all their code open source on GitHub. \nSo, I was able to just get a copy of that,  "
    } ]
  }, {
    "tStartMs": 976960,
    "dDurationMs": 6440,
    "segs": [ {
      "utf8": "clip on I Can't Believe It Can Sort, the latest \nand greatest sorting algorithm, and render out  "
    } ]
  }, {
    "tStartMs": 983400,
    "dDurationMs": 5160,
    "segs": [ {
      "utf8": "the visualization that you're looking at now. But, \nlet me be clear. What you're enjoying now is still  "
    } ]
  }, {
    "tStartMs": 988560,
    "dDurationMs": 7120,
    "segs": [ {
      "utf8": "100% Timo's excellent creative work, now with a \ntwist of Stanley's terrible sorting algorithm."
    } ]
  }, {
    "tStartMs": 1001720,
    "dDurationMs": 3320,
    "segs": [ {
      "utf8": "If you do watch that original video, you will \nrealize there's so many different sorting  "
    } ]
  }, {
    "tStartMs": 1005040,
    "dDurationMs": 4360,
    "segs": [ {
      "utf8": "algorithms out there. They all have pros and \ncons, features, things they do and don't do.  "
    } ]
  }, {
    "tStartMs": 1009400,
    "dDurationMs": 6200,
    "segs": [ {
      "utf8": "Some edit the list in place. Some duplicate \nthe list and then mess with that. Merge sort  "
    } ]
  }, {
    "tStartMs": 1015600,
    "dDurationMs": 3760,
    "segs": [ {
      "utf8": "splits the list into smaller and smaller lists.  "
    } ]
  }, {
    "tStartMs": 1019360,
    "dDurationMs": 6040,
    "segs": [ {
      "utf8": "And then when it recombines them all, the items \nend up in the correct order. And merge sort is  "
    } ]
  }, {
    "tStartMs": 1025960,
    "dDurationMs": 5280,
    "segs": [ {
      "utf8": "kind of practical. If you're wondering \nwhat is actually used, Python used to use  "
    } ]
  }, {
    "tStartMs": 1031240,
    "dDurationMs": 5160,
    "segs": [ {
      "utf8": "something called Tim sort. And it's called Tim \nsort because it was named after a guy called Tim.  "
    } ]
  }, {
    "tStartMs": 1036960,
    "dDurationMs": 8160,
    "segs": [ {
      "utf8": "Tim Peters invented it. And it's kind of a hybrid \nsort. It does use merge sort, but also use like  "
    } ]
  }, {
    "tStartMs": 1045120,
    "dDurationMs": 6600,
    "segs": [ {
      "utf8": "insertion sort. Cuz what it's doing is looking for \nsub sections of the data which are already sorted  "
    } ]
  }, {
    "tStartMs": 1052280,
    "dDurationMs": 5640,
    "segs": [ {
      "utf8": "and then capitalizes on that. Because some \nalgorithms are good for data that's completely  "
    } ]
  }, {
    "tStartMs": 1057920,
    "dDurationMs": 5320,
    "segs": [ {
      "utf8": "random, some are good if it's already basically \nsorted and a few are just in the wrong place, some  "
    } ]
  }, {
    "tStartMs": 1063240,
    "dDurationMs": 4560,
    "segs": [ {
      "utf8": "are good for long lists, some are good for short \nlists. So, your actual libraries, if you import  "
    } ]
  }, {
    "tStartMs": 1067800,
    "dDurationMs": 4680,
    "segs": [ {
      "utf8": "a sort method, will probably use a combination \nof different methods based on the data you're  "
    } ]
  }, {
    "tStartMs": 1072480,
    "dDurationMs": 8400,
    "segs": [ {
      "utf8": "putting into it. And Python now, Python 3, uses \npower sort, which sorts uh powerfully. Um yeah.  "
    } ]
  }, {
    "tStartMs": 1081920,
    "dDurationMs": 5120,
    "segs": [ {
      "utf8": "Look it up yourself. All jokes aside, because \nthat was technically a joke, you've got at the  "
    } ]
  }, {
    "tStartMs": 1087040,
    "dDurationMs": 6200,
    "segs": [ {
      "utf8": "extreme practical end now power sort. That's what \nPython 3 uses. At the other end of the useful to  "
    } ]
  }, {
    "tStartMs": 1093240,
    "dDurationMs": 6240,
    "segs": [ {
      "utf8": "ridiculous spectrum, you've got things like uh \nuh bogo sort. That's where you just randomly  "
    } ]
  }, {
    "tStartMs": 1099480,
    "dDurationMs": 5200,
    "segs": [ {
      "utf8": "keep shuffling the list until it's actually \nsorted. And you've got things like Thanos sort,  "
    } ]
  }, {
    "tStartMs": 1104680,
    "dDurationMs": 6320,
    "segs": [ {
      "utf8": "where you just randomly delete half the items in \nthe list until whatever's left is in the order  "
    } ]
  }, {
    "tStartMs": 1111000,
    "dDurationMs": 7760,
    "segs": [ {
      "utf8": "you want. And in the middle, you've got I can't \nbelieve it can sort, because it is ridiculous,  "
    } ]
  }, {
    "tStartMs": 1119400,
    "dDurationMs": 5800,
    "segs": [ {
      "utf8": "but it works. And it wasn't like deliberately \ndesigned to be a ridiculous sorting algorithm,  "
    } ]
  }, {
    "tStartMs": 1125200,
    "dDurationMs": 6080,
    "segs": [ {
      "utf8": "like some of the more esoteric ones, but it \nwasn't even designed to work, but it does. Ah,  "
    } ]
  }, {
    "tStartMs": 1131280,
    "dDurationMs": 4240,
    "segs": [ {
      "utf8": "which is why I love it so much. If you want \nto learn more about the sorting algorithms,  "
    } ]
  }, {
    "tStartMs": 1135520,
    "dDurationMs": 6040,
    "segs": [ {
      "utf8": "I'm going to link to actually a video by boot.dev. \nIt's really good. I came across it after I'd  "
    } ]
  }, {
    "tStartMs": 1141560,
    "dDurationMs": 7040,
    "segs": [ {
      "utf8": "already asked them to sponsor this video. Pure \ncoincidence. Nice video, link below. Don't forget,  "
    } ]
  }, {
    "tStartMs": 1148600,
    "dDurationMs": 7320,
    "segs": [ {
      "utf8": "25% off a one-year plan if you use my ridiculous \nQR code link in the description and that's it.  "
    } ]
  }, {
    "tStartMs": 1155920,
    "dDurationMs": 4120,
    "segs": [ {
      "utf8": "Have fun with your sorting algorithms and \nif you've got a favorite sorting algorithm,  "
    } ]
  }, {
    "tStartMs": 1160800,
    "dDurationMs": 5680,
    "segs": [ {
      "utf8": "put it in the comments below. I'll sort \nI'll sort by best sorting algorithm.  "
    } ]
  }, {
    "tStartMs": 1166480,
    "dDurationMs": 5160,
    "segs": [ {
      "utf8": "All right, I'll randomize them cuz I want to show \nyou sleep sort. This is where you assign a delay  "
    } ]
  }, {
    "tStartMs": 1171640,
    "dDurationMs": 5400,
    "segs": [ {
      "utf8": "for each one. This is quite small, 1 second. Each \ndelay is weighted, that's quite big, 5 seconds,  "
    } ]
  }, {
    "tStartMs": 1177040,
    "dDurationMs": 5280,
    "segs": [ {
      "utf8": "by how big it is. And if you assign a bunch of \ndelays, sleeps, they'll all then pop back up  "
    } ]
  }, {
    "tStartMs": 1182320,
    "dDurationMs": 6960,
    "segs": [ {
      "utf8": "again. They'll print to the screen in the order \nthat they're sized. Sleep sort. Ridiculous."
    } ]
  } ]
}