Description

You may have noticed that it's really hard to sort things efficiently. Well, that's where counting sort comes in!

Show Notes

This episode of the Basecs podcast is based on Vaidehi's blog post, Counting Linearly With Counting Sort from her basecs blog series.

Transcript

[00:00:00] SY: If you haven’t yet gotten your tickets for Codeland, you totally should. It’s our annual conference about all the wonderful things you can do with code. And besides great food, great talks, and great people, this year we’re offering complimentary on-site childcare. So bring your babies with you and see you there. For tickets, go to codelandconf.com.

[00:00:23] (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:30] VJ: And I’m Vaidehi Joshi, Author and Developer.

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

[00:00:37] VJ: Counting Sort.

[00:00:39] SY: This season of the Base.cs Podcast is brought to you by Linode. If you’ve got a personal project, a small business or a big business with lots of data, Linode offers you a 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:15] It’s also brought to you by Square. If you’re designing a website or building a mobile app, you’re probably going to want to take payments at some point. Square APIs allow you to easily implement their payment form on your website. And with their In-App Payments SDK, you can add it to your mobile app too. You don’t have to worry about dealing with PCI compliance because they’ll take care of that for you. Don’t let anything come between you and your money. Start building with Square over at squareup.com/go/codenewbie.

[00:01:48] SY: So we are back talking about sorts. I’m super excited. We talked about a bunch of sorts in the past. This one is called, “Counting Sort”. What is this one all about?

[00:01:58] VJ: It’s a sorting algorithm, as you might be able to guess, but it’s kind of like a special one and that you can’t use it on everything.

[00:02:07] SY: Oh, okay. Never mind.

[[00:02:09] VJ: It’s a little bit limited in what it can do, but it does do one thing very, very, very well and a super-efficient and fast and it’s great when you can use it in a certain scenario. But a lot of the times you can’t use it and many situations prevent us from using it which is why you may have never heard of it. But I guess I should tell you what it is.

[00:02:32] SY: Okay.

[00:02:33] VJ: I’m just talking about in the abstract, like it’s, you know, this guy at the party who’s not there, but I guess I should invite him in.

[00:02:40] SY: This is my Friday nights.

[00:02:44] VJ: So counting sort is an algorithm that basically has a couple rules that it has to follow in order for it to be implemented. So it’s like a very situational algorithm.

[00:02:53] SY: Very moody, very particular.

[00:02:55] VJ: So if it is so moody, what is a situation when it’s in a good mood and will actually work for you? Well, you can use counting sort on a set of numbers, set of integers, specifically, that needs to be sorted. So if you have a set of unsorted integers, you can use counting sort but only if you know the range of those integers, which means you know what the smallest one is and you know what the largest one is.

[00:03:23] SY: Okay.

[00:03:23] VJ: And if that range is pretty small.

[00:03:26] SY: We don’t like big ranges.

[00:03:27] VJ: No. Big ranges is not great and there are reasons for that as we will see when we start going through how this sorting algorithm works. But those are three limitations, right? You can only sort integers. So first of all, that’s like, “All right, well, there’s a lot of things out the window.”

[00:03:41] SY: It’s a pretty big limitation.

[00:03:43] VJ: But like, “All right, fine.” You want to sort numbers, fine. Say you do want to sort numbers, how often is it that you actually know what the largest and smallest value of those numbers is going to be?

[00:03:52] SY: That’s true. Yeah.

[00:03:54] VJ: Sometimes it’s fine. Like what if you’re like, “Okay, I have some items I want to sort on a page and I know it’s always going to be like zero through a hundred.” Great. Now you know the range, but like what if you have zero through a hundred thousand? Like, “Yeah, I know the range,” but that range is not small. You need it to be very small.

[00:04:10] SY: Yeah. This is a very finicky little thing.

[00:04:14] VJ: Yes. It’s very, very…

[00:04:15] SY: Very particular.

[00:04:17] VJ: Sassy.

[00:04:19] SY: It’s full of attitude.

[00:04:21] VJ: This is called a high maintenance algorithm.

[00:04:23] SY: If that is not a technical category of algorithms, it should be, the high maintenance category of algorithms. Yes. Okay. So how does this sorting algorithm actually work? Where do we start?

[00:04:38] VJ: Because this is counting sort, we are going to do some counting as the name would suggest. So there are a couple of steps to running a counting sort algorithm. I will tell you what they are and if they sound maybe a little bit strange, don't worry because we’ll go through them for a high level perspective on how counting sort works. If you have an unsorted set of integers and you know the smallest number and the largest number, you know the range of these, you can run counting sort by doing the following things. You will create a new array which is going to be a count array and you’re going to populate it with the number of times a certain number appears in the unsorted data set. So basically what I mean by that is you’re going to tally up the number of times you see every number.

[00:05:26] SY: I could do that.

[00:05:27] VJ: Then we’re going to cumulatively add up the values in our count array.

[00:05:33] SY: What’s that about?

[00:05:35] VJ: Well, if we’re going to go and tally the number of times that we see different values, we’re going to iterate through the count array and we’re going to say, “Okay, I’m going to just add up each value, each number of times with the previous neighboring element.” And it sounds strange.

[00:05:52] SY: Yeah, I’m going to need an example on that one for sure.

[00:05:53] VJ: But there are reasons.

[00:05:55] SY: Okay.

[00:05:56] VJ: The reasons are math, actually. That’s the reason.

[00:05:59] SY: The reasons are math. Okay. Good reason, good reason.

[00:06:01] VJ: Because math, as you may have heard, math. So once you cumulatively add up all the values in the count array, once you’ve populated it, you’re going to shift all the elements as Beyoncé did not say it to the right, to the right. We’re going to shift them over.

[00:06:22] SY: That’s a good one. Good job, Vaidehi. Very impressive.

[00:06:25] VJ: Thank you. So we’re going to shift all the elements in our count array by basically incrementing the index by one and then we’re going to create a new array which is not going to be a count array. It’s just going to be a new array that’s going to be the end result. It’s going to be the sorted elements.

[00:06:45] SY: Okay.

[00:06:46] VJ: The interesting thing about this is we have two arrays and a third empty array. We’re going to do an interesting little matching game basically where we’re going to take the index’s different elements and map them into their correct place in the new sorted array. So eventually what we’re going to have is we’re going to start off with this unsorted array. We’re going to use the count array to help us figure out how to sort and then we’re going to use those two arrays to populate a final third sorted array, which is going to be our sorted set of integers.

[00:07:15] SY: Okay. So there’s like a lot of stuff going on, right? There’s two arrays, there’s like a third array, they’re shifting, there’s cumulating, there’s a matching game, apparently. There’s a lot going on. Okay. I’m very excited to get to this example because that was a lot of information and now we’re going to see if we can connect the dots and flush things out a little bit.

[00:07:39] VJ: Sounds good.

[00:07:40] SY: So let’s start with a relatively simple array. It will have four numbers. Those numbers are 3, 2, 1, 3. Is that okay?

[00:07:51] VJ: Oh, it’s okay. I just wanted to say something.

[00:07:53] SY: Oh, what did you want to say?

[00:07:55] VJ: I wanted to say, “Look, there’s two 3s. There are duplicate values.”

[00:07:58] SY: Yeah. And I don’t know if we really mess with duplicates that much, right, when we do sorting arrays? Is it cool that we’re introducing one here?

[00:08:06] VJ: It’s totally cool actually and there’s some interesting stuff that counting sort will do with duplicates, but I just want to point out we do have duplicates and just don’t forget that we have duplicates.

[00:08:16] SY: Okay. I will not forget. Okay. So we have 3, 2, 1, 3. Again, that’s 3, 2, 1, 3. And so the first thing we’re going to do, you mentioned something about tallying. How does that work? How do we do that count array thing?

[00:08:32] VJ: So the first thing that we’re going to do is we have our set of unsorted numbers, right? 3, 2, 1, 3.

[00:08:37] SY: Yeah.

[00:08:38] VJ: We’re going to need a little helper array structure to help us do this counting sorting bit. So we’re going to create a new count array that’s going to have space for four elements in it. So it has indexes 0, 1, 2, 3, and this is going to be the place where we’re going to do this tallying.

[00:08:55] SY: Why does it have the four places? How do we get to four places? Is it because there are four numbers in the array or?

[00:09:00] VJ: It’s because we have our range of elements, right? Remember that we have to know our range of input numbers. So we start with 0 and we’re going to go up to the highest number that we have in our input. So that’s 3. So our numbers are 1, 2, 3. So we know, “Okay, the largest number is 3.” The lowest possible one we have here that could happen is 0, ever, because remember it’s integers. So we can’t have negative numbers. No, it can be.

[00:09:25] SY: I think it can be.

[00:09:27] VJ: It can be negative numbers. I’m thinking of rational numbers and then you could even have the negative numbers. But let’s just say for the case of this, we’re dealing with positive numbers. We’re dealing with the numbers.

[00:09:36] SY: Positivity.

[00:09:37] VJ: One through three here. We need to initialize, we need to create a new count array that’s going to have four possible slots in it because we’re dealing with counting the number 0, counting the number 1, the number 2, and the number 3.

[00:09:50] SY: Okay. Cool.

[00:09:51] VJ: Because we’re counting. This is where we’re going to do the population, the tallying.

[00:09:55] SY: So if we’re tallying, then I assume we start at 0 and then we ask, “Well, how many zeros do we have?” And then we have 0, 0. So we don’t have any zeros at all. So then we would populate that zero index with the value 0. Okay.

[00:10:11] VJ: And if you think about it from a programmatic perspective, the way that you described it is like, “How many zeros you pass through the whole array?” And you’re like, “How many zeros?” We’re doing that because we’re human and that’s like the way we think about it. But if a computer was doing this, if you’re writing a loop when you were doing this, you would just go from the first element and you would say, “What element is this? Oh, it’s a 3. I’m going to mark the I have a 3.”

[00:10:34] SY: Okay. Let’s do it that way then because I want to be like a computer.

[00:10:36] VJ: Great. Me too. Who doesn’t?

[00:10:38] SY: Right. Who doesn’t? Computer is so cool. Okay. So if we start with the first value, 3, then I’d go, “Okay, how many 3s do I have?” Well, so far I only have that one 3. So then I go to my 3 index and I tally that so I add the value 1.

[00:10:58] VJ: All you’re doing is just incrementing. You’re bumping it up. As soon as you see a number, you’re like, “Okay, let me go to the index that is the value of this number.” So if you see the number 3, you go to index 3 in the count array.

[00:11:08] SY: Yeah.

[00:11:08] VJ: And you’re like, “All right, I saw one. I’m just going to mark that I saw one. I’m not doing anything fancy, no sparkles, no confetti. Just marking things down.”

[00:11:16] SY: Okay. Okay. Nice and simple. Okay. So then we go to the next number, which is number 2. We go to index 2 and then we increment that by 1. Then we go to our next number in our unsorted array, which is the number 1, we go to index 1, and we increment that value by 1. Then we go to our last number, which is the number 3, we go back to index 3. Remember we were there at the very beginning and now we increment that number 1 to number 2.

[00:11:41] VJ: Exactly. And so now what you have is you have this count array and when you look at it, you see that there’s nothing at index 0. You see that at index 1, there’s a number 1. At index 2, there’s the number 1 and at index 3, there’s a number 2. And basically looking at this, you kind of get a snapshot of all the numbers we’re dealing with. So we can see, “Oh, there are no zeros, but there are two 3 and there’s one 2, and there’s also one 1.”

[00:12:05] SY: Yeah. Yeah. It’s interesting because I feel like when we talk about into indices and values, I feel like we spend so much time focusing on the values and that’s always the star. But in this case, the indices are the stars, right? Because we’ve taken our initial values and we’ve kind of matched them up. We’ve transformed them almost to indices.

[00:12:27] VJ: And you know what? I said there were no sparkles or confetti, but you know what? The indices are the confetti. Like they are magical the way that it works out in this algorithm. We’re going to see more of that like later on when we get two or three steps down, but it’s pretty cool. You picked up something important, which is that the indices are the real star of the show.

[00:12:47] SY: Okay. All right, so we have our count array which as you said is 0, 1, 1, 2. Now what? What do we do next?

[00:12:54] VJ: So now we’re going to do the bit that sounded weird when I was explaining the steps, which is the cumulatively adding up step. And all that means is we’re going to go through the count array, which right now looks like 0, 1, 1, 2. And for each element in it, we’re going to take that value, go to the next element and sum them together, and that’s going to become the new value. So what I mean by that is we’ll start at 0. I have nobody to the left of it. It’s the first element, right? So there’s no one to add it to, which is fine. So then we go to its neighbor, its right door neighbor, its right next door neighbor, and the next element is 1. And in this case, now I have something to add 0 to. So I’m going to say, “Oh, 0 and 1, I’m going to add them together and that’s going to become the new value of this element at index 1.”

[00:13:42] SY: Okay.

[00:13:43] VJ: So I’m going to say, “Oh, what’s 0 plus 1? It’s one.” That’s fine.

[00:13:46] SY: So nothing has changed so far.

[00:13:48] VJ: Correct. Nothing has changed so far.

[00:13:49] SY: Right, because the 1 used to be there and now the 1 is still going to be the one.

[00:13:51] VJ: It’s still there.

[00:13:53] SY: Okay.

[00:13:53] VJ: And then I’m going to keep doing that same step till I get to the end of the array. So we’re going to repeat that same process again with 1’s next door neighbor. So remember, our count array is 0, 1, 1, 2. We added 0 and 1 together, nothing about 1 changed. Now we’re going to add 1 and its neighbor together, 1 plus 1 is 2. So now the element at index 2 is not 1. We’ve now changed it. We’ve cumulatively added it and it’s now 2 and we’re going to do…

[00:14:21] SY: Can I do the last one?

[00:14:22] VJ: Yeah. Yeah. So far our updated count array is 0, 1, 2. So now we’re going to look at 2’s neighbor which has the value 2. So we’re going to add those two together. So 2 plus 2 equals 4. So my last index, which is my index number 3, the value of that index is now going to be 4.

[00:14:45] VJ: Exactly.

[00:14:46] SY: So what used to be 0, 1, 1, 2 is now 0, 1, 2, 4.

[00:14:52] VJ: And the way we got, all we did was we iterated through the array, the count array, remember, not the unsorted one, the count array.

[00:14:59] SY: Yes, count array.

[00:14:59] VJ: I want to be specific because I know there’s a lot of arrays happening here. All we do is we iterated through the count array and for each element that we found we just cumulatively added its value to its next door neighbor.

[00:15:14] SY: That wasn’t as bad as I thought. I was a little worried at the beginning. But yeah, I think that makes sense.

[00:15:19] VJ: Yeah. We just keep adding the previous value to the next, get to the end of the array, and now we’ve done that crazy step.

[00:15:25] SY: Okay. Okay. So that’s done. That’s good. Now what do we do next?

[00:15:31] VJ: Now Beyoncé is going to come over and she’s going to be like, “Everything to the right.”

[00:15:35] SY: Okay. Okay.

[00:15:36] VJ: And what I mean by that is we’re just going to shift over all the elements. So here’s the interesting thing. We have at index 0 we have 0, at index 1 we have 1, at index 2 we have 2, and index 3 we have 4.

[00:15:51] SY: Yes.

[00:15:51] VJ: If we shift everything over, now 4 is going to have nowhere to go. So it’s just going to fall off the array and leave.

[00:15:57] SY: That’s true. Oh, no. It’s exited the party. It’s like, “I’m done. I’ve had my fun. It’s time for me to go home.”

[00:16:06] VJ: So we’ve shifted over everything. So now our count array looks like… well, there’s nothing at index 0 because we just shift it over and there’s nothing to shift over, right? But now at index 1, we have the number 0, which used to be at index 0. And at index 2, we have the number 1, which used to be at index 1. And at index 3, we have the number 2, which used to be at index 2.

[00:16:28] SY: So we did the cumulatively adding. We have done some shifting. So now our count array reads… but what do we do with that empty space? It was like nothing there. We just leave it as nothing? Like what do we do with it?

[00:16:43] VJ: So I said it was nothing, but actually it’s going to be just the number 0 because when we started, remember when we started off the count array, I said that we are going to start off with this new count array and we’re going to initialize it and we’ll tally up everything because we start off not knowing how many like happens to be in our unsorted collection. Everything just starts with 0. And as we go through the unsorted collection and we start tallying, we increment it, right? So it starts at 0 and it maybe goes up to 1, 2, 3, depending on how many of that number exists. So we reset the value to be 0. So in the case of shifting over everything, at index 0 we just have the number 0 because…

[00:17:24] SY: We’re resetting basically.

[00:17:25] VJ: Exactly.

[00:17:26] SY: Okay, that makes sense. Okay. So our count array now reads 0, 0, 1, 2. So we’ve done like a bunch of stuff with that count array. We have populated it then we cumulatively added things. Then we shifted things over. We’re really going in on this count array. You know, at this point honestly, Vaidehi, I’m just kind of trusting that this will end up with this order because so far I feel like we’re doing a bunch of really random, disconnected mathy things. So I’m just trusting that eventually we will find ourselves in a place where we have a sorted array.

[00:18:02] VJ: Yes.

[00:18:03] SY: So what do we do next?

[00:18:04] VJ: we will. Okay. So to recap, we have two arrays, right? We have our unsorted array, the original thing we started with.

[00:18:11] SY: Not like a long time ago.

[00:18:12] VJ: Yeah. That wasn’t that long ago. And now we have this helper array, this count array that we’ve done all these things to. And now we’re going to leverage these two arrays to help us come up with our sorted array. The last step involves us creating a new array, which is where we’re going to put these sorted elements. So we’re going to say, “New array.” It has four spots in it because we have four elements to sort and we’re going to look at our unsorted array and we’re just going to go through it. And for each element, we’re going to kind of pull that element aside and say, “Hey, whatever your number is, whatever you are, go find your index in the count array.” And they will see you at your proper place. And that’s where you should live in the sorted array. We kind of have this count array as the intermediary step to help us figure out where each unsorted element should go to make it sorted correctly. So do you want to try going through that?

[00:19:11] SY: Okay. Sure. Sure. Yeah. Okay. I’m so excited. Okay. So we have our number 3. That’s the first number in our unsorted array. So we take our number 3 then we go to our count array. Okay. So you said I’m going to take the number 3. I’m going to find the 3 index and then I’m going to look at its value, its value is the number 2. So what I just did is I said, “Okay, 3, go find where you’re going to live. You’re going to live at number 2.”

[00:19:41] VJ: Yeah, and the way you did that is by telling the number 3, “Okay, go find the equivalent index of yourself in the count array.”

[00:19:49] SY: Yes. Go find yourself.

[00:19:52] VJ: Or like, “Go stand in the line for things that look like you.” The way I like to think about it is if you go to a show, like imagine you’re like going to the ballet or something and you have to go pick up your tickets at will call and when you get to will call, this is like a very elaborate ballet center, theater.

[00:20:09] SY: A ballet center theater. The Ballet Center Theater, yes.

[00:20:13] VJ: It’s very elaborate and they have a whole system. So when you go to will call, you see all these little lines that you can stand in by last name.

[00:20:20] SY: Okay.

[00:20:21] VJ: Okay. So like my last name is Joshi. So I would go stand in the line for people with last names J. And when I get to that line, they give me my ticket and they say, “You are sitting here,” and that’s how I figure out where I belong. When the show starts, that’s where I know I’m going to sit.

[00:20:35] SY: Yeah. Yeah.

[00:20:36] VJ: So it’s like a similar thing we’re doing here where we are going through each person, each number in line, right? And for example with the number 3, we said, “Okay, 3, go stand in the line with the other 3s.”

[00:20:46] SY: All the other 3s. Yeah.

[00:20:48] VJ: “And they’ll figure out what to do with you.” Of course, we’re going one by one, so there aren’t any other 3s right now. But we pull off 3 and we say, “Hey, 3, since you are the number 3, go to index 3” because it matches who you are and they’ll tell you where to go, 3 goes to the index 3, and at index 3 the value is 2, and that’s where 3 knows to go into the sorted array. So right now at this point, our sorted array, which is the new array we created to help us sort, is literally just 0, 0, 3, 0. There’s nothing else in it.

[00:21:21] SY: Because you’re the first person in the theater and you just sat down.

[00:21:25] VJ: Actually I’m wrong. I don’t even want to say that it’s zero because zero could be a number. So it’s more of like empty 3s. Yes.

[00:21:33] SY: Yes, empty seat, empty seat.

[00:21:34] VJ: Empty, empty 3, empty.

[00:21:36] SY: Okay. So once I sit down, do I need to do anything? Am I done? Can I move on to the next number?

[00:21:42] VJ: So Win 3 is sitting down. Win 3 is in its spot, in the array. Remember back at the beginning of this episode when I said that there are duplicates?

[00:21:50] SY: Yes.

[00:21:51] VJ: If we don’t do something right now, if we don’t take a special step right now, we’re going to have problems if there’s another 3 down the road, which surprise there is.

[00:22:00] SY: A plot twist, there is. Yeah.

[00:22:02] VJ: So basically because you don’t want two numbers to sit exactly, you know, one on top of the other because you can’t do that in an array.

[00:22:08] SY: That would not be fun. You can’t see the ballet.

[00:22:10] VJ: Yeah, you can’t see a ballet if someone’s sitting on you. That’s very true. Win 3 says, “Okay, I’ve got my seat. Thank you. Bye.” 3 gets put into its correct spot. Now at the will call booth 3, which is basically the count array. At the count array, we need to increment the value. Otherwise, the next time a number 3 shows up, it’ll go to the spot 2. We don’t want to do that. So we’re going to increment 2 to be 3.

[00:22:38] SY: So that if there is another number 3 down the line, which there is, then it will get a different seat.

[00:22:45] VJ: Exactly. But basically at that point we’re done with the number 3. It’s been sorted.

[00:22:49] SY: Okay.

[00:22:49] VJ: Do you want to try doing the next one?

[00:22:51] SY: Sure, I’d love to. Okay. So we have number 2. So number 2 is going to go to will call, it’s going to find this little section, and it’s going to find the value for its seat, which is number 1.

[00:23:03] VJ: Yup.

[00:23:04] SY: So now I’m going to go to my sorted array which is basically my theater and I’m going to say, “Okay, I’m going to go to seat number 1. I’m going to put myself there.” So at this point, our sorted array is empty, 2, 3, and then empty. So there are two people seated in my ballet.

[00:23:21] VJ: Yes. This is a very small four-person audience ballet, but that’s fine.

[00:23:25] SY: And it still needs will call because…

[00:23:29] VJ: Yes.

[00:23:30] SY: Because we said so. Okay. So what’s the other one? So let’s do the next number which is the number 1. The number 1 goes to the…

[00:23:40] VJ: Did we increment the last one?

[00:23:42] SY: Oh, no. Oh my goodness. How could I? I did not increment. We don’t want people sitting on top of each other. Okay. So now that 2 has been seated, we’re going to go back to our count array and we’re going to increment the value so that instead of a 1, it’s now a 2. So that just in case that we have another 2 coming along, maybe it’s a late arrival, it will have its own seat and it will not sit on top of my original number 2.

[00:24:05] VJ: Yup. So then we have our next number, which is number 1. So again, I’m going to stand in line in my count array. I’m going to get a value of 0. I’m going to now go to my sorted array. I’m going to find my index 0, which is my seat, and I’m going to put myself there. So now my sorted array reads 1, 2, 3, empty. And now that I have sat in my proper seat, I’m going to increment and turn that 0 back in my count array to 1.

[00:24:38] VJ: Yup.

[00:24:39] SY: All right. Okay. We have one more to go, one more to go. Almost done. Okay. So now we have our number 3. So we’re going to go to the count array and we’re going to find the number 3. We’re going to stand in line and find number 3 and now because we have incremented from the first number 3 we had, we see a number 3 waiting for us. We have a number three value. So now we’re going to take that number 3 and we’re going to our seat and we’re going to sit down at the number 3 index and we’re going to put ourselves there.

[00:25:11] VJ: Yup.

[00:25:11] SY: So now our sorted array reads 1, 2, 3, 3.

[00:25:15] VJ: Yup. And now they’re all sorted.

[00:25:18] SY: Yeah. We don’t even need to increment or anything because we’re all done.

[00:25:21] VJ: Exactly.

[00:25:22] SY: Wow! I did not think that was going to come together, by the way. I was like, “I don’t know what she’s doing. She’s got all these arrays going. She’s doing god-knows-what to this single count array.” I don’t know where you’re going with that.

[00:25:33] VJ: I just pushed another number off the array.

[00:25:37] SY: You kicked out number 4.

[00:25:38] VJ: Homicides here.

[00:25:41] SY: Casualties all over the place. It’s a crime scene. I don’t know what was going on. Okay.

[00:25:46] VJ: Well, the cool thing here is all of that just…

[00:25:49] SY: It works.

[00:25:49] VJ: Well, yeah, that’s the first thing. It worked, right? The other cool thing is that it all lined up at the end with the count array helping us make sense of the unsorted array and turning it into the sorted array, right? Like that count array was like this little magical box that with the indices that we had it all just magically fell into place.

[00:26:09] SY: Yes.

[00:26:10] VJ: And that is hashing happening there. That’s like the stuff we talked about with like hash tables and hashing algorithms. This was basically us like hashing, hashing out. We’re just hashing out how to sort through this and that’s what counting sort basically abstracts away from you. You know?

[00:26:29] SY: Yeah.

[00:26:30] VJ: And it works out because you have this limited number of integers to deal with and you know the smallest and you know the largest because if you can imagine if we did this with a very large data set and we were coming up within a count array and we were like, “Oh, I have five numbers, but I have to create a count array between 0 to 500,” maybe that’s not the best thing because you’re going to have a lot of zeros and then you’re going to be cumulatively incrementing and then you’re going to shift everything over and you’re just kind of like, “Why are we doing this?”

[00:27:02] SY: This is not what I signed up for. Yeah.

[00:27:03] VJ: Yeah. But in our example, it was okay. But that sort of illustrates to you like we have some hashing going on, we have a little bit of math, we have this intermediary array to help us, and all of these things together help us work with an algorithm that ends up being very close to linear time. It’s nearly linear time.

[00:27:22] SY: Oh, that’s a good one.

[00:27:24] VJ: Yeah.

[00:27:25] SY: So this algorithm is basically better than all the other algorithms we’ve talked about, right, in terms of performance?

[00:27:31] VJ: Yeah. We’ve talked about linearithmic, we’ve talked about things that are really bad like a quadratic, but we’ve daydreamed about a linear time algorithm. We haven’t actually I don’t think seen one and this counting sort runs very close to linear time. It does require a little bit of extra space because the duplicate array. But if you find yourself having to deal with a small data set of integers specifically and you know what the range is going to be and the range is not too big, then, hey, you could very well be efficient about it with counting sort and we now know it magically does work, except it’s not magic, it’s math.

[00:28:12] SY: It’s not magic, it’s math. Okay, very, very cool. And that’s the end of today’s show. If you like 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 shout out to Linode for sponsoring the show. Linode is giving you a chance to try their powerful servers built for all your infrastructure needs. They’ve got nine data centers worldwide with new data centers opening this year in India and Canada. Getting started with a shiny new server takes less than one minute so you can get up and running in no time and you can get a $20 credit by using the promo code CodeNewbie2019. Just go to linode.com/codenewbie for more info. And want to say thank you to Square. Square has APIs and SDKs to make taking payments easy whether you’re building a mobile app in iOS, Android, Flutter, or React Native. If you want to embed a checkout experience into your website, it’s super easy. Square has processed billions of transactions so you know it’s tried and true. Start building with Square over at squareup.com/go/CodeNewbie. This episode was edited and mixed by Levi Sharpe.

[00:29:24] VJ: Bye everyone.

[00:29:25] SY: Thanks for listening. See you next week.