Description

We learn all about our second "divide and conquer" algorithm, quick sort! We walk through how it works with help from a queendom, a few pointers, and a very helpful pivot number.

Show Notes

This episode of the Basecs podcast is based on Vaidehi's blog post, Pivoting To Understand Quicksort [Part 1] from her basecs blog series.

Transcript

[00:00:02] (Music) Welcome to the Base.cs Podcast where we explore the basics of computer science concepts. I’m your host Saron, founder of CodeNewbie.

[00:00:09] VJ: And I’m Vaidehi Joshi, Author and Developer.

[00:00:12] SY: And she is the brilliant mind behind the Base.cs Blog Series. Today we’re talking about.

[00:00:16] VJ: Quicksort.

[00:00:19] SY: This season of the Base.cs Podcast is brought to you by our wonderful friends at DigitalOcean. DigitalOcean provides the easiest cloud platform to deploy, manage, and scale applications of any size. They remove infrastructure friction and provide predictability so you can spend more time building what you love. Try DigitalOcean for free by going to DO.co/codenewbie and get $100 in infrastructure credit. Link is in your show notes.

[00:00:47] This season is also brought to you by the fine folks at Linode. If you’ve got a personal project, a small business or a big business with lots of data, Linode offers you secure hosting for all your infrastructure needs. They are a Linux cloud hosting provider where you can get a new server up and running in under a minute. Plans start at one gigabytes of RAM for just five bucks a month. And with the promo code CodeNewbie2019, you can get a $20 credit. So go to linode.com/codenewbie and give it a try. Also, they’re hiring. Check out their jobs at linode.com/careers. Link is in your show notes.

[00:01:25] SY: Okay, let’s get started. Quicksort. Okay, so we have been talking about a bunch of different sorting algorithms. We’ve talked about selection sort, insertion sort. What’s another one? We did another too.

[00:01:41] VJ: Ah… Merge sort.

[00:01:42] SY: Merge sort. That’s true.

[00:01:43] VJ: Oh, bubble, bubble sort. That’s the one that I always try to not remember. And it works. I didn’t remember it till end.

[00:01:51] SY: There you go. Mission accomplished. So we’ve talked about four different sorting algorithms and bubble sort, insertion sort, selection sort were all…bleh... that was what they were. They were all…bleh.

[00:02:05] VJ: That’s a technical term.

[00:02:06] SY: And then merge sort, however, is getting better. We have some hope in merge sort.

[00:02:10] VJ: Things got better. It improved faster.

[00:02:12] SY: Things are looking up, things are moving faster, we’re progressing in our lives. And with quicksort, I’m hoping we are staying in this new life, in this new world of awesomeness. Is that what we’re going to do?

[00:02:24] VJ: We are. We’re going to stay in this world.

[00:02:26] SY: Okay. Will we be staying and going through this life very quickly?

[00:02:32] VJ: Ha-ha-ha.

[00:02:35] SY: Yeah. We’ll see. Hopefully, it means it’s fast and efficient. We’ll find out. Okay. Let’s define it. What is quicksort? What is this thing?

[00:02:42] VJ: So quicksort is a sorting algorithm that has one characteristic that should be familiar to us already. In last week’s episode, we talked about merge sort and we went kind of into some detail about why it is an efficient algorithm and one of the things we talked about was the fact that it’s a divide-and-conquer algorithm. When you design an algorithm that way you basically find a solution that works for the smallest version of that problem. So you find a solution that works on a sub problem and you apply it to the larger problem at hand. So quicksort does the same thing.

[00:03:15] SY: Okay.

[00:03:16] VJ: The interesting part is how it does that. It chooses a pivot point in an unsorted collection.

[00:03:23] SY: Okay.

[00:03:24] VJ: And based on that pivot point, it divides or partitions the collection such that all the elements smaller than the pivot come before it and all the elements larger than the pivot come after it.

[00:03:38] SY: Okay. So this sounds familiar with the merge sort because we kind of have like a… it wasn’t called a pivot number. What do we have? We had something kind of like that, right?

[00:03:47] VJ: It was like the middle point I think is what we called it with merge sort.

[00:03:49] SY: Middle point. Okay. That’s what I was thinking of. Yeah. So same idea of having like one number that helps us in our dividing and conquering.

[00:03:57] VJ: It does a little bit differently, but same idea of like having a middle piece. But interestingly with pivot, it’s not necessarily just the middle element.

[00:04:05] SY: Okay. So this pivot piece, I’m trying to imagine my mind how this works. So I have my pivot number and I have my unsorted list. So now what do I do?

[00:04:17] VJ: You have this pivot number and you have your unsorted list and what you’re basically trying to do is use the pivot in order to do a certain level of sorting, I guess, you could say.

[00:04:29] SY: Okay.

[00:04:29] VJ: What you’re basically doing is you’re using the pivot and you’re basically going to divide your list such that everything is sorted in relation to the pivot. So what that means is you will kind of divide your list and move all the elements smaller than the pivot to one side to the left side and all the elements larger to the right side, but that doesn’t mean they’re all sorted when we do it. All it means is they’re sorted in comparison to the pivot and what it is. So you kind of like do a pseudo sort, sort of. You like vaguely sort it.

[00:05:01] SY: A loose sort.

[00:05:03] VJ: Yeah, I like that, loose sort. Yeah.

[00:05:05] SY: Okay. So this pivot number that we’re talking about, does it have to be any particular numbers? Can I just kind of pick whatever number I want? How does that work?

[00:05:14] VJ: The pivot is extremely crucial to the quicksort algorithm. And for now, we’ll just say that the number that we want for our pivot should kind of be in the middle of our data set. I guess we could say it’s the median number. Usually a lot of quick sort algorithms will sort of arbitrarily pick a number. In an ideal world, if you could just do the right thing, you’d pick the median of your data set and use that to sort.

[00:05:42] SY: Okay. So just to make sure I have this high level understanding of it, so I have let’s say a list of subjects and they are standing in a row.

[00:05:53] VJ: Wait, wait, wait. List of subjects?

[00:05:55] SY: Yeah, like people.

[00:05:57] VJ: Who is the queen here?

[00:05:58] SY: Oh, obviously, it’s me.

[00:06:01] VJ: I was like, “Subjects?”

[00:06:01] SY: Clearly.

[00:06:02] VJ: Whose kingdom, queendom? In what situation are we in?

[00:06:06] SY: In my queendom. It’s a beautiful queendom. Everyone is very happy. Everyone knows how to code. They don’t have computer science degrees because they don’t need them because they have this podcast. Youknow It’s just a wonderful place to be.

[00:06:17] VJ: It’s quiet. It’s very quiet.

[00:06:21] SY: It’s a very quiet queendom. Yes. So today on this rare occasion, they are standing in line with their headphones out off. And so as the queen, I am the pivot and I want to sort them by height. I want the shortest people all the way to the tallest people. Okay? We’re going to sort them by height. So what we’re doing with this quicksort situation is I as the pivot would say, “Okay, you are shorter than me, so I’m going to put you to the left of me. And then you over there, you’re taller than me, so I’m going to put you to the right of me. And then you over there, you’re shorter than me too so now you’re going to be on the left. You’re taller than me, I’ll be putting you on the right,” and just keep going like that so that everything to my left is shorter than me, everything to my right is taller than me. It’s almost like I made like a little sub list, right?

[00:07:18] VJ: Uh-hmm.

[00:07:18] SY: Amongst each sub list they are not sorted.

[00:07:21] VJ: Exactly. Yeah, because you’re their queen, I guess.

[00:07:24] SY: That’s right.

[00:07:26] VJ: They are sorting themselves in relation to you and not to each other. The only guarantee there is, is that they are going to be shorter than you on one side, not necessarily shorter than you and also shorter than the person to their right but taller than the person to their left.

[00:07:43] SY: Okay. So that seems like a good first step, but I assume we are not done because we are not sorted. So once we have divided, well, we’ve kind of divided them sort of because there’s like a left side and right side. What happens next?

[00:08:00] VJ: Well, I have some bad news for your queendom. There’s about to be a coup.

[00:08:03] SY: No!

[00:08:04] VJ: Actually there’s going to be two coups, which is very complicated.

[00:08:06] SY: Seriously?

[00:08:08] VJ: Yeah. Now that I think about it, the political side of this is a very, very complicated. Just don’t worry about that part. Basically since you mentioned earlier, you have two sub lists, right? You have the sub list of subjects on your left and the sub list of subjects on your right. They’ve been partitioned. They’ve been divided into two halves, but they also need to be sorted in relation to each other. But because this is a divide-and-conquer algorithm, we want to use the same basic steps, the same rules to sort the sub list too. In order to sort them, we’re going to do what we just did with the larger sub list, which means each sub list needs to choose its own pivot.

[00:08:51] SY: Oh, Interesting. But what happens to me?

[00:08:55] VJ: Oh, you just stand there and stay where you are as the queen.

[00:08:58] SY: Well, at least I get to keep my throne. It’s nice.

[00:09:01] VJ: Yeah.

[00:09:02] SY: Okay. So what do these two new pivots do? What happens to them?

[00:09:05] VJ: For example, let’s just focus on one. I think it’s a little bit easier and then we’ll get an idea of what the second one is doing because, hint, it’s the same thing.

[00:09:12] SY: Okay.

[00:09:15] VJ: So let’s say the subjects that are smaller than you, you have a sub list on your left, they kind of will you know step to one side, if you can imagine them stepping to one side, and they are going to say, “Okay, we need to choose our own pivot,” and they’re going to choose a pivot the same way that you as the queen pivot was chosen. So let’s say you were the pivot at the end of the list, so we just picked you. In the sub list we’ll do the same thing. We’ll pick the last element and we’ll say, “Okay, you’re the new pivot.”

[00:09:43] SY: Okay.

[00:09:43] VJ: Now all the elements that are to your one side, we’re going to sort them in relation to you, new pivot. And then when the new pivot finds its correct home, it’s right spot, it will move over there and any elements that still need to be sorted will become a sub sub-list.

[00:10:04] SY: Oh!

[00:10:05] VJ: And then they’ll pick their own pivot and it’ll keep happening until it gets down to the point of a sorted list.

[00:10:12] SY: Oh, so that sub list gets smaller and smaller because we’re making like sub, sub, sub, sub lists until we’ve run out of anything to put in our list basically.

[00:10:25] VJ: Yeah, until we’ve basically gone down to a completely sorted list, which is usually like a situation where you have the one element on its own or you have like a sub list and it’s just like two elements and you were like, “Okay, I’ll sort them. Here’s the pivot. Here’s the element that’s larger than it or that’s smaller than it.” And you’re like, “Okay, well, I have a pivot and something in relation to it and it’s in its right place.”

[00:10:50] SY: Okay.

[00:10:50] VJ: But you have a bunch of sorted sub lists, if that makes sense.

[00:10:53] SY: Because at the end of each sub list sorting, what ends up happening is the pivot finds its place. So eventually all the numbers will be pivots and eventually all the pivotal find their place and then at that point you’re sorted.

[00:11:08] VJ: Yeah, up until the point where every pivot has been sorted into its correct place, you aren’t completely done with the algorithm right. And when you have got every single pivot, every single sub list has been sorted down to its smallest parts. Now you have a bunch of sorted sub lists. And when once you have sorted sub list, you can put the whole kingdom back together again because you have told everyone to go sort themselves out, pun sort of intended and then you kind of just have them all come back together again and they’re sorted in relation to the original pivot and to their little pivots that they elected in these little coups. Do you elect in a coup?

[00:11:55] SY: Yeah. I was wondering about the logistics of a coup organization. I’m not particularly sure about how that works. But sure, let’s have a coup election.

[00:12:03] VJ: Sure. Yeah.

[00:12:05] SY: Okay. Cool. So it’s interesting that we’re kind of repeating and doing the same thing over and over again, right? Because we started with ultimately the best pivot, which is me, the pivot queen, and then for some reason the soldiers weren’t happy they divided and picked their own little two pivots and did the same thing. And then once that pivot was in its right place, they put a new pivot and do the same thing. So this is starting to feel recursive.

[00:12:34] VJ: It is. Actually divide and conquer and recursion go hand in hand because you know the moment that you’re like repeating the same steps for you know a sub problem, a sub problem or like a sub list within a sub list, you’re like, “Oh, I’m doing the same thing. I can implement this recursively.” That is basically what happens with divide and conquer.

[00:12:51] SY: Okay. So this makes sense to me on a high level, but I think I need an example to really figure out the mechanism of this. So can we do a quick example?

[00:13:03] VJ: Let’s do it.

[00:13:03] SY: Okay. So let’s say we have an array and the array has five numbers. The numbers are 9, 1, 6, 2, 5, and we talked about how we can pick the pivot in a number different ways. One of the ways is that it’s at the end. So we’ll pick 5 because that’s the last number that we have in our array.

[00:13:23] VJ: Yup. Easy.

[00:13:24] SY: Nice and easy. Yes. So we have our 9, 1, 6, 2, 5 with 5 as our pivot. So now that we have 5 as our pivot, from the example with me being queen, we talked about how now we’re going to sort all the other numbers in relation to that 5. Like how do we actually do that? What do we do next?

[00:13:49] VJ: Well, we know what we’re kind of trying to achieve on a high level, right? We’re trying to kind of say, “Five, you stand here in the middle and all the ones, all of the little numbers that are smaller than you, you move to the left, and all the big numbers that are bigger than you, go to the right.” That’s what we’re trying to do.

[00:14:05] SY: Right.

[00:14:07] VJ: But we don’t want to create an extra array and copy things over or like you know make a copy of an array and iterate and all that. We don’t really want to do that. We’re trying to be a little clever here.

[00:14:16] SY: Okay.

[00:14:16] VJ: So instead of doing this algorithm out of place, we’re going to do it in place, which means we are going to use references. We’re going to move things around without duplicating them and we’re going to figure out the right place to move them and we’re just going to swap some stuff.

[00:14:33] SY: Okay.

[00:14:34] VJ: That’s all.

[00:14:35] SY: All right. How many references do we need?

[00:14:38] VJ: We just need two, I think. We could say that we have like a pseudo reference to our pivot because we have to know what the pivot is, but for now let’s just say we have two because those are the two we really need to focus on.

[00:14:50] SY: Okay.

[00:14:51] VJ: And the two that we’ll have are going to be what we’re going to use to split up our list into the left half and the right half. So we have 9, 1, 6, 2, 5 we’ll start by just saying, “Five, you just move over a little bit, move to the side. We’re not dealing with you right now.”

[00:15:09] SY: Step aside.

[00:15:10] VJ: Exactly. So really what we’re looking at, at the moment is 9, 1, 6, 2.

[00:15:13] SY: Okay.

[00:15:14] VJ: And we’re going to start with a left reference starting at the leftmost edge of the list and a right reference that starts at the rightmost edge. So if we’re ignoring the pivot since we have 9, 1, 6, 2, our left reference is going to be 9 and our right reference is going to be 2.

[00:15:31] SY: Okay.

[00:15:31] VJ: So what we want to do is, remember, we’re trying to move elements smaller than our pivot to the left and elements larger than our pivot to the right, but what we have is something interesting here, the left reference, so right now the thing that’s on the left side of the list, is the number 9 and the right reference, the thing that’s on the right side of the list, is the number 2.

[00:15:54] SY: Oh, that’s bad.

[00:15:55] VJ: Yes. Things are not in the right place.

[00:15:57] SY: Yeah, because 9 is, well, obviously 9 is bigger than 5. So we want that to actually be on the right side and the two, which is less than 5, we want that to be on the left side. So can we just like swap them?

[00:16:14] VJ: We should swap them because we know 2 should be on the left side of the list because it’s smaller than 5 and 9 which is in comparison to our pivot larger than 5 should be on the right side. So since we know this and we’re like looking at these two pointers and we’re like, “Oh, when we compare them to the pivot, we know they’re on the wrong spot. We could just swap them.” And so now if we swap them and we’re just moving elements around, now our list reads 2, 1, 6, 9, and 5 over there.

[00:16:40] SY: Okay. Okay. So what happens to our pointers? Because we have the left pointer that used to be on 9. Is it now a 2?

[00:16:52] VJ: It is, yeah, still at the same spot.

[00:16:54] SY: Right, right, still the same index.

[00:16:55] VJ: The reference, the left reference was just all it really cared about was what index it was in the array and the right reference similarly only focused on what index it was on the array. The left reference is still pointing the first element and the right reference is still pointing to the last element. It just so happens now that the elements have been swapped.

[00:17:12] SY: Okay. Okay. That makes sense. Okay. So now that they’ve been swapped, the reference… by the way, can we call them pointers? Is that the same thing or are they different?

[00:17:20] VJ: Yeah. They’re equivalent.

[00:17:21] SY: Okay. So the pointers, they are going to stay you know where they are for now anyway, and then well what happens next?

[00:17:32] VJ: Well, now that we know that the left pointer is smaller than 5 and the right pointer is larger than 5, just so we remember the left pointer is now 2 and the right pointer is now 9. Now we know these two elements are going to end up in the correct place in the list.

[00:17:48] SY: Okay.

[00:17:50] VJ: So now what we can basically do is shift our pointers because we’ve dealt with those numbers in comparison to our pivot.

[00:17:56] SY: Okay.

[00:17:57] VJ: So our list was 2, 1, 6, 9, and 5, which is the pivot. We’ll ignore it for now, 2, 1, 6, 9. We’re going to increment our pointers. So now our left pointer moves from 2 to 1 and our right pointer moves from 9 to 6.

[00:18:13] SY: Okay. So at this point after the pointers have moved, it’s still 2, 1, 6, 9, and then the 5, which we ignore, but the pointers are in different spots, so the left pointer is now at 1, the right pointer is now at 6. So I assume we will be comparing the 1 to the 5 and the 6 to the 5.

[00:18:31] VJ: Yeah, that’s exactly right.

[00:18:33] SY: Does one of the pointers go first in that comparison? Does it like matter?

[00:18:39] VJ: So we’re going to basically look at the left pointer first. And if you remember when we kind of started in the first version when 9 was at the beginning of the list and 2 was at the end, we started and we said, “Oh, 9 in comparison to 5 is bigger.” Then we looked at the right pointer and we said, “Two in comparison to five is smaller.” And that’s how we got down this road of swapping. We looked at 9 first. So we looked at the left pointer first. So we’re going to want to follow the same steps again for all the iterations. And if we are dividing and conquering, then we want to continue to do that same order of operations in order to make this algorithm work.

[00:19:18] SY: Okay. So the pattern is usually left-right, left-right in terms of the pointers. Okay. So then we would look at the left pointer first, which is pointing at the number 1, compare it to 5 and 1 is less than 5 and we want the numbers that are less than 5 to be on the left side. So the 1 is actually fine. We’re happy with 1.

[00:19:41] VJ: Yeah, 1 is in the right place and we’re like, “Okay, this left reference is less than our pivot and so we’re fine,” and so we can look at the right reference and eventually something interesting is going to happen actually. Let’s go through it.

[00:19:53] SY: Okay, I’m excited. Okay. So now we are looking at our right pointer, which is pointing at the number 6, we compare it to our pivot which is the number 5, 6 is bigger than 5 which means we want 6 to be on the right side and it is. So the 6 is fine as well.

[00:20:10] VJ: Exactly. So there’s nothing to do here, right? One is in the spot. Our left point is fine. Our right pointer is also fine, 6 is in the right spot. So we’re just going to increment again. Remember, our list is 2, 1, 6, 9, and our left pointer is at 1 and our right pointer is at 6. So now we’re going to increment the left pointer from 1 over but now our left pointer is pointing to 6 and our right pointer is also at 6 at this very moment. We really should be incrementing it to 1. We should basically be crossing over. Our pointers are going to finally intersect.

[00:20:48] SY: That’s weird.

[00:20:49] VJ: Yeah, interesting. But also it’s like the fact that our pointers are intersecting basically means we’ve looked through the whole list, right?

[00:20:56] SY: Yeah, because I was going to say we’re kind of done, how does the algorithm know that we’re done? But I guess it’s this crossing over moment that signals the end.

[00:21:04] VJ: Basically. Basically what happens is like once the index of our left pointer is greater than or equal to the index of the right pointer, we know the crossover has happened. And that’s when we finally know that in relation to the pivot all these numbers are basically on the correct side. So there’s one big step left.

[00:21:30] SY: Okay. What is it?

[00:21:31] VJ: We got to do something with the pivot.

[00:21:33] SY: Oh, okay. So we told it to go off to the side. We said, “Move aside, pivot,” but now we’re bringing it back.

[00:21:40] VJ: Yes. So we know after going through our numbers that 2 and 1 are both smaller than 5.

[00:21:46] SY: Yes.

[00:21:46] VJ: We just looked at the number 1, which is our left pointer and we incremented it. So now we know everything on that side should be on the left of our pivot.

[00:21:57] SY: Which it is, right?

[00:21:59] VJ: It is. And so we know that the pivot needs to go after those numbers.

[00:22:04] SY: Ah. Okay. Okay. Got it. How do we do that?

[00:22:08] VJ: So once the index of our left reference is greater than or equal to the index of the right reference, we can basically swap the pivot with the element at the left reference. So in this case, we’ve incremented our left reference, our left pointer to the number 6. And so we’re like, “Okay, now I know the pointers have intersected. My left reference is pointing at 6. Time to swap the pivot.” And the pivot is going to go where the 6 is going to is actually sitting right now and the 6 has to take the pivot spot because remember we’re doing everything in place so you have to like who everything around.

[00:22:50] SY: Everything is a swap.

[00:22:51] VJ: Yeah. So now our new list reads 2, 1, 5, 9, 6. If we just look at everything to the left of 5, we’re looking at 2 and 1. And we look at everything to the right of 5, we’re looking at 9 and 6.

[00:23:12] SY: Yeah.

[00:23:12] VJ: Now 2 and 1 are both smaller than 5.

[00:23:15] SY: That’s true.

[00:23:17] VJ: But they’re not in the right order.

[00:23:19] SY: That is true too.

[00:23:19] VJ: And 9 and 6 are also both larger than 5, but they’re also not in the right order.

[00:23:25] SY: No, they’re not.

[00:23:26] VJ: But they are in the right order in comparison to our initial pivot. So we have somewhat loosely sorted our list.

[00:23:34] SY: Okay. So now we’ve done essentially like one round. Is that a fair way to describe it?

[00:23:39] VJ: Yeah. Yeah. We split our one list, our initial list into a pivot with two sub lists basically, so we’ve done one round.

[00:23:48] SY: And left sub list is 2, 1, right sub list is 9, 6, which is very exciting. So with our 2, 1, 5, 9, 6 we need a new pivot.

[00:23:58] SY: We need two new pivots actually.

[00:23:59] SY: Oh my God, you’re right. We do need two new pivots.

[00:24:02] VJ: Because we got two sub lists.

[00:24:04] SY: Each sub list needs its own pivot. Okay. So, we, I think you said..how did you say that we’re going to pick them from earlier?

[00:24:11] VJ: Well, we’re going to stick with the same thing we’ve done before. So what we did in the beginning of this algorithm was we just picked the last number of the sub list and we made that the pivot kind of arbitrarily.

[00:24:20] SY: Okay. So if we look at the left sub list that pivot would be 1 because it’s just 2, 1 and the last one is just 1. And then if we look at the right sub list, it is 9, 6 and the last number is 6 so the pivot will be 6.

[00:24:38] VJ: So our whole collection reads 2, 1, 5, 9, 6, but the 5 is going to stay in its own spot. So we got 2, 1, our 1 is our left pivot, our new left pivot, and 9, 6, and 6 is going to be the new pivot for the right side.

[00:24:53] SY: Okay. So if we focus on the left sub list first, can I have a go and what we have is first? Okay. So in our left sub list, we have only a 2 and a 1.

[00:25:02] VJ: Yup.

[00:25:03] SY: I don’t think there’s much for us to do. Because we have our.. So technically, we have to have our left pointer and it’s going to point at 2, but a we don’t really have a right pointer, like we can’t, right?

[00:25:16] VJ: Yeah, in this case you basically you’ll have a left pointer and you’ll compare it to the pivot and you’ll say, “Oh, it’s larger,” and you are going to have to swap it with the only element that there’s left to swap with.

[00:25:29] SY: Which is the pivot.

[00:25:29] VJ: Yup.

[00:25:30] SY: Okay. So the left sub list now reads 1, 2. Done. Nailed it. Okay. So now we’re onto our right sub list, which is 9, 6 and we decided that the pivot is going to be the last number so the pivot is 6. So we are going to get our left pointer, which is going to be pointing to the number 9 and we’re going to compare it with the pivot which is 6 and it is greater than 6. There’s no really right pointers or something else to compare it to and we know that 9 should be on the right of 6. So we just swap 9 and 6.

[00:26:05] VJ: Yup.

[00:26:05] SY: And if we do that and we read the full array, it would read 1, 2, 5, 6, 9.

[00:26:11] VJ: And our list is sorted. Yeah.

[00:26:13] SY: And it’s sorted. Wow! Okay. You said something early on though where you said that once we were done we were going to have a bunch of sub lists but then we have to put them together. Is there like another step that we now need to do once things are sorted?

[00:26:28] VJ: Well, I guess the putting together is the fact that you have to sort every single sub list, which I guess is really the dividing. So I guess the putting together here is a little bit misleading because we did have to divide everything up in order to sort it. But because this is an algorithm that’s in place, we’re not like you know putting arrays together or merging writing elements together. When we did merge sort, we did actually have to, you know, upon the elements.

[00:27:01] SY: Yeah. That’s what I was thinking of.

[00:27:03] VJ: This is an in place algorithm and we’re using references so we didn’t ever take anything apart really. So we don’t really have to put together. We did everything with pointer. So it was all in place and so all of the sorting was happening with just one collection. We didn’t make duplicates. We didn’t split it up. We just move things around and we shifted around in a specific order.

[00:27:24] SY: Yeah. It sounds efficient. It sounds like a really efficient way of doing things. Does it have a really good Big O notation?

[00:27:33] VJ: It is actually pretty efficient. It’s got a reputation of being one of the most efficient algorithms actually when it comes to sorting, but I’m going to do one of my favorite things. I’m going to leave you on a cliffhanger and I’m going to save the Big O notation of quicksort for next episode.

[00:27:50] SY: Okay. Okay. I’m excited for that.

[00:27:55] VJ: The bigness of O?

[00:27:56] SY: Yes. Yes, the bigness of that O. Oh, I love that. I love that. And that’s the end of today’s show. If you liked what you heard, please leave us a review and make sure to check out Vaidehi’s blog post. Link is in your show notes. Also want to give a huge thank you to Linode for sponsoring the show. Try their powerful servers built for all your infrastructure needs. Getting started with a shiny new server takes less than one minute so you can get up and running in no time. Get a $20 credit by using the promo code CodeNewbie2019. Just go to linode.com/codenewbie for more info. Also want to give a huge shout-out to DigitalOcean. They are the easiest way to deploy, manage, and scale your application. Everything about it was built with simplicity at the forefront; setting, deploying, even billing. Try DigitalOcean for free by going to DO.co/codenewbie and get $100 in infrastructure credit. Link is in your show notes. Vaidehi, you want to say goodbye?

[00:28:54] VJ: Bye everyone!

[00:28:55] SY: Thanks for listening. See you next week.