You'd probably look at this two different ways. One, you could say that this is way too easy. Students either in changing the variable names is exactly in code, is in CS awesome for insertion sorting? So that one can be interesting things to discuss, you could argue that. The other thing you could argue is it's really, really difficult, because this code looks really complex, and especially if you didn't call it mystery sort, of course, I would say sorts an array correctly, it could seem pretty hard. I think both of those questions or comments are legitimate. Let me tell you why I do it. First, by saying mystery sort, I want to be able to reinforce with my students the difference between insertion sort, where we loop over everything going up and then we're keeping this sorted section and we're going down and we're putting it in there as a while loop versus selection sort, which has two for loops. Really, it's an excuse to talk through this code in detail, because when I'm doing my classroom discussion questions, my computers are off, and the kids aren't on CS awesome and they can't just lean on running the code. So I want them to be able to work through them, and this is really important, we're going to find out shortly, because some of the multiple choice question assessment opportunities around sorts, and especially for APCSA, are going to involve students being able to trace this code in depth, in detail. They will have to create their own sorts, selection, or insertion, but they're going to have to be able to trace some code, maybe find bugs in it, etc. This is a lot of time and effort to build up these sorts of explanations, and even so, I find them less than satisfying than doing it with kids in the classroom, and there's no Greek, there's a whole lot of videos out there on them and I still can't find one that I really like, especially in a way that ties to the code, and get the big overview ones but tying to the code, they tend to be very boring and like somebody talking at the screen. So how does insertion sort work? Again, our idea is we're going to start, I'm going to say the one at the bottom, we're going to have that and we're going to see if this item here, the next item over, where should we insert that in there? So we start at the first element, and we're going to work our way to the right, that's what that big for loop says. Start at j equal 1, while j less than elements.length, so that sounds good. This is where I want students to be reminded. I love that video that show the cards on it. The idea is, I'm going to pick up an item or the card off the table, and I've got this hand of cards here so that item I picked up is temp. Now I got to figure out where to insert it in here, and my hands of cards is sorted, so I'm going to go down and we're going to go look through and when I find the places should go, I'll put it there. This is an image of that that I think is helpful for students. So picking the card off the table, that's like putting the 3 into temp, and at the very end, I'll tell you one of the things that's really bad about these diagrams, but for now, go with it, 3 gets put into temp, that's what happens before the loop. In this part, this is the going from right to left, starting at this spot, that's what we started with at j, and we're trying to find the possible index where it goes in. Does it go in here? Does it go in there? Does it go in there? So that my hands stay sorted. So we're going to try to find the correct place to insert. In our diagram here, that's going to be, because we're trying to put 3, we need to find and put 3 in that place, that's going to be the correct place for this particular example. Then afterwards, we have to do one more thing, which is to insert the card into your hand at the correct place, which we actually just showed a video over here, that picture, the 3 actually goes in the right place. So again, the card we picked up off the table, blah blah blah, find the right index, put it in there. So the while loop is moving right to left to find that right index. How do we know this is the right place? Well, yeah, let's think about that a little bit. So again, it's the right place because when I put it in, it's going to stay in sorted order, but what does that look like in code? What it looks like in code is that I asked the ArrayList at the iterator, the possible index iterator I'm looking at, minus one, the one that would come before it, if that item there is smaller than temp, then this is the place it should go in, because I'll be passing by things that are bigger than it, until I get to something that is smaller than the one I want to insert, and then it goes right there. So that is really important to point out here on the code. So we start this possible index of a pair of j, because we just took this out of the j spot. We're actually going to be looking at possible index, while possible index is greater than zero, meaning I haven't gotten to the end or the beginning of my ArrayList, and the temp is less than possible index minus one. So that says it's not at the end of the array. The thing I'm trying to insert my temp is smaller than the thing one spot to the left of where you pick me up at the first time, and then eventually, its possible index is going to change. So how does that actually work in our diagram? So we already put three up in the temp. That's the first image up on the top. That happened before the loop. When we get to the loop header, that's right in between the boundary of those two pictures. We're asking is three, which is temp less than the thing that's in my hand that's just to the left of it, that's the eight. Is three less than eight? Yes, it is. I'm not going to cover that, getting all that is your part. So the answer is three less than eight?Yeah, it is. So I need to keep looking because this eight here, it's too big, I'm smaller than it. Then we go to the next thing. So j would be decreasing by one. Then we'd say, okay, we're going to move that eight up or show the code, do that in a minute. Is three less than five? So I'm going one more over, and if that's true, three less than five? Yeah. Then I go one more spot, and then I get asking right after the bottom image there, is three less than two? No. So that's when I break out of the loop. I don't copy that, move the two over one, I go to down loop, and then that's where I put that temp gets inserted at possible index. So insert your card into your hand at the correct place. Yes, thank you. So again, before the loop, we pull out the number that were the next one is inserted in the right place, put it into temp. We have in this case, two iterations inside the loop. We're trying to find the right place to stick it in because it needs smaller than eight, and it's smaller than five, but it's not smaller than two. So we check that loop iterator for the third time, but then we don't execute the loop body, we jump down and we go. After the loop, we stick temp into the correct possible index. So my loop header was what we're following on that. Whether there's a code inside doing, this is copying something from the left to the right. Possible index minus one, which we just checked and we said, oh, I'm still smaller than that. I need to move you up. So moving, copying things up to the right, and then we're moving our index down to the left. Here's the final biggest teacher tip I think I've ever put on a slide, and may be really important for you that you might not have thought of yet. Pretty much any animation you can find of sorting gets the following thing wrong, as do all the ones that I've shown you. That assigning a value to a new place, like assigning the three into temp, it doesn't move it or remove it from the old place like in the ArrayList, it just makes a copy of it. But it doesn't make it seems to make it less clear or something, I don't know about what's exactly happening, but it's true. You can go back and watch all the animations we've probably shown you so far and you'll find this is true. They always make it like, it moves it from one place to another. No, it's copying. We actually get to copy, like clone it, and then move it into the temp variable. So in this case, just to be really clear, when we move the ArrayList sub j, I think, into temp, there's actually a three still in the ArrayList, and a three in the temp array variable. There's two threes because that's what assignment does. This is also one of the reasons it's very hard to act this out in person because you'd be tempted to have the students be the numbers and like walk around, but the thing is when I'm number three, and I was in the space of ArrayList at index 0, 1, 2, 3, I can't just go walk to temp. I've done this once in class, I'm not sure if I really recommend it, but I would give people multiple pieces of paper and a marker, and I'd be like, okay, you need to assign your value into temp. They would take the piece of paper and write their three on it, and then hand in a copy of it to the temp variable to represent that we each have our own copy of that value.
