Algorithms and Data Structures Tutorial - Full Course for Beginners

This is a full-length course from Treehouse. We at Free Code Camp are longtime fans of their learning platform. They were kind enough to let our non-profit make this course freely available on our YouTube channel. If you like this course, Treehouse has a lot more courses like this one. The link is in the description along with time codes to the different sections in this course. [Music]

Hi, my name is Passan. I'm an instructor here at Treehouse, and welcome to Introduction to Algorithms. Whether you are a high school or college student, a developer in the industry, or someone who is learning to code, you have undoubtedly run into the term algorithm. For many people, this word is kind of scary. It represents this body of knowledge that seems just out of reach; only people with computer science degrees know about algorithms. Now, to others, this brings up feelings of imposter syndrome. You might already know how to code, but you're not a real developer because you don't know anything about algorithms. Personally, it made me frame certain jobs as above my skill level because the interview contained algorithm questions.

Well, whatever your reasons are, in this course, our goal is to dispel all those feelings and get you comfortable with the basics of algorithms. Like any other subject, I like to start my courses with what the course is and is not. In this course, we're going to cover the very basic set of knowledge that you need as a foundation for learning about algorithms. This course is less about specific algorithms and more about the tools you will need to evaluate algorithms, understand how they perform, compare them to each other, and make a statement about the utility of an algorithm in a given context.

Now, don't worry; none of this will be theoretical, and we will learn these concepts by using well-known algorithms. In this course, we will also be writing code, so I do expect you to have some programming experience if you intend to continue with this topic. You can definitely stick around even if you don't know how to code, but you might want to learn the basics of programming in the meantime. In this course, we will be using the Python programming language. Python reads a lot like regular English and is the language you will most likely encounter when learning about algorithms these days. If you don't know how to code, or if you know how to code in a different language, check out the notes section of this video for links to other content that might be useful to you. As long as you understand the fundamentals of programming, you should be able to follow along pretty well. If you're a JavaScript developer or a student who's learning JavaScript, for example, chances are good that you'll still be able to understand the code we write later. I'll be sure to provide links along the way if you need anything to follow up on.

Let's start with something simple: What is an algorithm? An algorithm is a set of steps or instructions for completing a task. This might sound like an oversimplification, but really, that's precisely what an algorithm is. A recipe is an algorithm; your morning routine when you wake up is an algorithm; and the driving directions you follow to get to a destination is also an algorithm. In computer science, the term algorithm more specifically means the set of steps a program takes to finish a task. If you've written code before—any code, really—generally speaking, you have written an algorithm.

Given that much of the code we write can be considered an algorithm, what do people mean when they say you should know about algorithms? Now consider this: Let's say I'm a teacher in a classroom, and I tell everyone I have an assignment for them on their desks. They have a picture of a maze, and their task is to come up with a way to find the quickest way out of the maze. Everyone does their thing and comes up with a solution. Every single one of these solutions is a viable solution and is a valid example of an algorithm—the steps one needs to take to get out of the maze. But, from being in classrooms or any group of any sort, you know that some people will have better ideas than others. We all have a diverse array of skill sets. Over time, our class picks the best of these solutions, and any time we want to solve a maze, we go with one of these solutions. This is what the field of algorithms is about. There are many problems in computer science, but some of them are pretty common, regardless of what project you're working on. Different people have come up with different solutions to these common problems, and over time, the field of computer science has identified several that do the job well for a given task. When we talk of algorithms, we're referring to two points: We're primarily saying there's an established body of knowledge on how to solve particular problems well, and it's important to know what the solutions are.

Now, why is it important? If you're unaware that a solution exists, you might try to come up with one yourself, and there's a likelihood that your solution won't be as good or efficient—whatever that means—compared to those that have been thoroughly reviewed. But there's a second component to it as well. Part of understanding algorithms is not just knowing that an algorithm exists but understanding when to apply it. Understanding when to apply an algorithm requires properly understanding the problem at hand, and this arguably is the most important part of learning about algorithms and data structures. As you progress through this content, you should be able to look at a problem and break it down into distinct steps. When you have a set of steps, you should then be able to identify which algorithm or data structure is best for the task at hand. This concept is called algorithmic thinking, and it's something we're going to try and cultivate together as we work through our content. Lastly, learning about algorithms gives you a deeper understanding about complexity and efficiency in programming. Having a better sense of how your code will perform in different situations is something that you'll always want to develop and hone. Algorithmic thinking is why algorithms also come up in big tech interviews. Interviewers don't care as much that you are able to write a specific algorithm in code, but more about the fact that you can break a seemingly insurmountable problem into distinct components and identify the right tools to solve each distinct component. And that is what we plan on doing in this course. Though we're going to focus on some of the tools and concepts you'll need to be aware of before we can dive into the topic of algorithms, if you're ready, let's get started.

Hey again! In this video, we're going to do something unusual: We're going to play a game. And by "we," I mean me and my two friends here, Brittany and John. This game is really simple, and you may have played it before. It goes something like this: I'm going to think of a number between 1 and 10, and they have to guess what the number is. Easy, right? When they guess a number, I'll tell them if their guess is too high or too low. The winner is the one with the fewest tries. All right, John, let's start with you. I'm thinking of a number between one and ten. What is it? Between you and me, the answer is three. Uh, quick question: Does the range include one and ten? That is a really good question. So what John did right there was to establish the bounds of our problem. No solution works on every problem, and an important part of algorithmic thinking is to clearly define what the problem set is and clarify what values count as inputs. Yeah, 1 and 10 are both included. Is it one? Too low. Is it two? Too low. Is it three? Correct. Okay, so that was an easy one. It took John three tries to get the answer. Let's switch over to Brittany and play another round using the same number as the answer. Okay, Brittany, I'm thinking of a number between 1 and 10 inclusive, so both 1 and 10 are in the range. What number am I thinking of? Is it 5? Too high. 2? Too low. Is it 3? Correct. All right, so what we had there was two very different ways of playing the same game. Somehow, with even such a simple game, we saw different approaches to figuring out a solution. To go back to algorithmic thinking for a second, this means that with any given problem, there's no one best solution. Instead, what we should try and figure out is what solution works better for the current problem. In this first pass at the game, they both took the same amount of turns to find the answer, so it's not obvious who has the better approach, and that's mostly because the game was easy. Let's try this one more time. Now this time the answer is 10. All right, John, you first. Is it one? Too low. Is it two? Still too low. Is it three? Too low. Is it four? Too low. Is it five? Still too low. Is it six? Too low. Is it seven? Too low. Is it eight? Low. Is it nine? Low. Is it ten? Correct. You got it. Okay, so now same thing but with Brittany this time. Is it five? Too low. Eight? Too low. Is it nine? Still too low. It's ten. All right, so here we start to see a difference between their strategies. When the answer was three, they both took the same number of turns. This is important. When the number was larger, but not that much larger—10 in this case—we start to see that Brittany's strategy did better. She took four tries while John took 10. We've played two rounds so far, and we've seen a different set of results based on the number they were looking for. If you look at John's way of doing things, then the answer being 10—the round we just played—is his worst-case scenario. He will take the maximum number of turns, 10, to guess it. When we picked a random number like three, it was hard to differentiate which strategy was better because they both performed exactly the same, but in John's worst-case scenario, a clear winner in terms of strategy emerges. In terms of algorithmic thinking, we're starting to get a sense that the specific value they're searching for may not matter as much as where that value lies in the range that they've been given. Identifying this helps us understand our problem better. Let's do this again for a range of numbers from one to one hundred. We'll start by picking five as an answer to trick them.

Okay, so this time we're going to run through the exercise again, this time from one to one hundred, and both one and one hundred are included. Is it one? At this point, without even having to run through it, we can guess how many tries John is going to take. Since he starts at one and keeps going, he's going to take five tries, as we're about to see. Is it five? Cool, correct. Okay, now for Brittany's turn. Is it 50? Too high. Is it 25? Still too high. Is it 13? Too high. Is it seven? Too high. Is it four? Too low. Is it six? Too high. Is it five? Correct. Let's evaluate: John took five tries; Brittany, on the other hand, takes seven tries, so John wins this round. But again, in determining whose strategy is preferred, there's no clear winner right now. What this tells us is that it's not particularly useful to look at the easy answers where we arrive at the number fairly quickly because it's at the start of the range. Instead, let's try one where we know John is going to do poorly. Let's look at his worst-case scenario where the answer is 100 and see how Brittany performs in such a scenario. Okay, John, let's do this one more time, one through 100 again. Is it one? We can fast-forward this scene because, well, we know what happens. John takes 100 tries. Hi, Brittany, you're up. Is it 50? Too low. Is it 75? Too low. 88? Too low. 94? Too low. Is it 97? Too low. 99? Too low. 100. Okay, so that took Brittany seven turns again, and this time she is the clear winner. If you compare their individual performances for the same number set, you'll see that Brittany's approach leaves John's in the dust. When the answer was five—so right around the start of the range—John took five turns, but when the answer was 100—right at the end of the range—he took 100 tries. It took him 20 times the amount of tries to get that answer compared to Brittany. On the other hand, if you compare Brittany's efforts when the number was 5, she took seven tries, but when the number was 100, she took the same amount of tries. This is pretty impressive. If we pretend that the number of tries is the number of seconds it takes Brittany and John to run through their attempts, this is a good estimate for how fast their solutions are. Okay, we've done this a couple of times, and Brittany and John are getting tired. Let's take a break. In the next video, we'll talk about the point of this exercise.

In the last video, we ran through an exercise where I had some of my co-workers guess what number I was thinking. So, what was the point of that exercise? You might be thinking, "Hey, I thought I was here to learn about algorithms." The exercise we just did was an example of a real-life situation you will run into when building websites, apps, and writing code. Both approaches taken by John and Brittany to find the number I was thinking of are examples of searching for a value. It might be weird to think that there's more than one way to search, but as you saw in the game, the speed at which the result was obtained differed between John and Brittany. Think about this problem from the perspective of a company like Facebook. At the time of this recording, Facebook has 2.19 billion active users. Let's say you're traveling in a different country and meet someone you want to add on Facebook. You go into the search bar and type out this person's name. If we simplify how the Facebook app works, it has to search across these 2.19 billion records and find the person you are looking for. The speed at which you find this person really matters. Imagine what kind of experience it would be if, when you search for a friend, Facebook put up a spinning activity indicator and said, "Come back in a couple of hours." I don't think we'd use Facebook as much if that was the case. From the company's perspective, working on making search as fast as possible using different strategies really matters.

Now I said that the two strategies Brittany and John used were examples of search; more specifically, these are search algorithms. The strategy John took, where he started at the beginning of the range and just counted one number after the other, is a type of search called linear search. It is also called sequential search, which is a better description of how it works, or even simple search, since it really is quite simple. But what makes his approach an algorithm as opposed to just looking for something? Remember, we said that an algorithm is a set of steps or instructions to complete a task. Linear search is a search algorithm, and we can define it like this: We start at the beginning of the list or the range of values; then we compare the current value to the target. If the current value is the target value that we're looking for, we're done. If it's not, we'll move on sequentially to the next value in the list, and then repeat step 2. If we reach the end of the list, then the target value is not in the list. This definition has nothing to do with programming, and in fact, you can use it in the real world. For example, I could tell you to walk into a bookstore and find me a particular book, and one of the ways you could do it is using the linear search algorithm. You could start at the front of the bookstore and read the cover or the spine of every book to check that it matches the book that you're looking for. If it doesn't, you go to the next book and repeat until you find it or run out of books. What makes this an algorithm is the specificity of how it is defined in contrast to just jumping into a problem and solving it as we go along. An algorithm follows a certain set of guidelines, and we use the same steps to solve the problem each time we face it. An important first step to defining the algorithm isn't the algorithm itself, but the problem we're trying to solve. Our first guideline is that an algorithm must have a clear problem statement. It's pretty hard to define an instruction set when you don't have a clear idea of what problem you're trying to solve. In defining the problem, we need to specify how the input is defined and what the output looks like when the algorithm has done its job. For linear search, the input can be generally described as a series of values, and the output is a value matching the one we're looking for. Right now, we're trying to stay away from anything code-related, so this problem statement definition is pretty generic, but once we get to code, we can actually tighten this up. Once we have a problem, an algorithm is a set of steps that solves this problem. Given that, the next guideline is that an algorithm definition must contain a specific set of instructions in a particular order. We really need to be clear about the order in which these instructions are executed. Taking our simple definition of linear search, if I switched up the order and said, "Move sequentially to the next value" before specifying that first comparison step, if the first value were the target one, our algorithm wouldn't find it because we moved to the second value before comparing. Now you might think, "Okay, that's just an avoidable mistake and kind of common sense." The thing is, computers don't know any of that and just do exactly as we tell them, so specific order is really important. The third guideline is that each step in our algorithm definition must not be a complex one and needs to be explicitly clear. What I mean by that is that you shouldn't be able to break down any of the steps into further into additional subtasks. Each step needs to be a distinct one. We can't define linear search as "search until you find this value" because that can be interpreted in many ways and further broken down into many more steps. It's not clear. Next, and this one might seem obvious, but algorithms should produce a result. If it didn't, how would we know whether the algorithm works or not? To be able to verify that our algorithm works correctly, we need a result. Now, when using a search algorithm, the end result can actually be nothing, which indicates that the value wasn't found, but that's perfectly fine. There are several ways to represent nothing in code, and as long as the algorithm can produce some results, we can understand its behavior. The last guideline is that the algorithm should actually complete and cannot take an infinite amount of time. If we let John loose in the world's largest library and asked him to find a novel, we have no way of knowing whether he succeeded or not unless he came back to us with a result.

Okay, so quick recap: What makes an algorithm an algorithm and not just something you do? One: It needs to have a clearly defined problem statement, input, and output. When using linear search, the input needs to be just a series of values, but to actually use Brittany's strategy, there's one additional precondition, so to speak. If you think about her strategy, it required that the numbers be sorted in ascending order. This means that where the input for John is just a series of values to solve the problem, the input to Brittany's algorithm needs to be a sorted series of values. So, clearly defined problem statement, clearly defined input, and clearly defined output. Second: The steps in the algorithm need to be in a very specific order. The steps also need to be distinct; you should not be able to break it down into further subtasks. Next: The algorithm should produce a result. And finally: The algorithm should complete in a finite amount of time. These guidelines not only help us define what an algorithm is, but also helps us verify that the algorithm is correct. Executing the steps in an algorithm for a given input must result in the same output every time. If, in the game I played, the answer was 50 every time, then every single time John must take 50 turns to find out that the answer is 50. If somehow he takes 50 turns in one round then 30 the next, we technically don't have a correct algorithm. Consistent results for the same set of values is how we know that the algorithm is correct. I should stress that we're not going to be designing any algorithms on our own, and we'll start off and spend most of our time learning the tried and true algorithms that are known to efficiently solve problems. The reason for talking about what makes for a good algorithm, though, is that the same set of guidelines makes for good algorithmic thinking, which is one of...

The most important skills we want to cultivate when we encounter a problem: before rushing in and thinking about solutions, what we want to do is work through the guidelines first. We break down the problem into any possible number of smaller problems, where each problem can be clearly defined in terms of an input and an output.

Now that we know how to generally define an algorithm, let's talk about what it means to have a good algorithm. An important thing to keep in mind is that there's no one single way to measure whether an algorithm is the right solution, because it is all about context. Earlier, we touched on two concepts: correctness and efficiency. Let's define correctness more clearly, because before we can evaluate an algorithm on efficiency, we need to ensure its correctness.

Before we define our algorithms, we start by defining our problem. In the definition of that problem, we have a clearly defined input satisfying any preconditions and a clearly defined output. An algorithm is deemed correct if, on every run of the algorithm against all possible values in the input data, we always get the output we expect. Part of correctness means that, for any possible input, the algorithm should always terminate or end. If these two are not true, then our algorithm isn't correct.

If you were to pick up an algorithm's textbook and look up correctness, you will run into a bunch of mathematical theory. This is because traditionally algorithm correctness is proved by mathematical induction, which is a form of reasoning used in mathematics to verify that a statement is correct. This approach involves writing what is called a specification and a correctness proof. We won't be going into that in this course. Proof through induction is an important part of designing algorithms, but we're confident that you can understand algorithms both in terms of how and when to use them without getting into the math. So if you pick up a textbook and feel daunted, don't worry, I do too, but we can still figure things out without it.

All right, so once we have a correct algorithm, we can start to talk about how efficient an algorithm is. Remember that this efficiency ultimately matters because they help us solve problems faster and deliver a better end-user experience in a variety of fields. For example, algorithms are used in the sequencing of DNA, and more efficient sequencing algorithms allow us to research and understand diseases better and faster. But let's not get ahead of ourselves; we'll start simple by evaluating John's linear search algorithm in terms of its efficiency.

First, what do we mean by efficiency? There are two measures of efficiency when it comes to algorithms: time and space. Sounds really cool and very sci-fi, huh? Efficiency measured by time, something you'll hear called time complexity, is a measure of how long it takes the algorithm to run. Time complexity can be understood generally outside the context of code and computers, because how long it takes to complete a job is a universal measure of efficiency; the less time you take, the more efficient you are. The second measure of efficiency is called space complexity, and this is pretty computer-specific; it deals with the amount of memory taken up on the computer. Good algorithms need to balance between these two measures to be useful. For example, you can have a blazingly fast algorithm, but it might not matter if the algorithm consumes more memory than you have available. Both of these concepts, time and space complexity, are measured using the same metric, but it is a very technical-sounding metric, so let's build up to it slowly and start simple.

A few videos ago, I played a game with Brittany and John where they tried to guess the number I was thinking of. Effectively, they were searching for a value. So how do we figure out how efficient each algorithm is and which algorithm was more suited to our purposes? If we consider the number of tries they took to guess or search for the value as an indicator of the time they take to run through the exercise, this is a good indicator of how long the algorithm runs for a given set of values. This measurement is called the running time of an algorithm, and we'll use it to define time complexity.

In the game, we played it four rounds; let's recap those here, focusing on John's performance. In round one, we had 10 values; the target was 3, and John took 3 turns. In round 2, we had 10 values; the target was 10, and John took 10 turns. In round 3, we had 100 values; the target was [unspecified], and John took five tries. And finally, in round four, when the target was 100 given 100 values, John took 100 tries. On paper, it's hard to gauge anything about this performance. When it comes to anything with numbers though, I like to put it up on a graph and compare visually. On the vertical or y-axis, let's measure the number of tries it took John to guess the answer, or the running time of the algorithm. On the horizontal or x-axis, what do we put for each turn? We have a number of values as well as a target value. We could plot the target value on the horizontal axis, but that leaves some context and meaning behind. It's far more impressive that John took five tries when the range went up to 100 than when he took three tries for a maximum of 10 values. We could plot the maximum range of values, but then we're leaving out the other half of the picture. There are data points, however, that satisfy both requirements. If we only plot the values where the target, the number John was looking for, was the same as the maximum range of values, we have a data point that includes both the size of the data set as well as his effort.

There's an additional benefit to this approach as well. There are three ways we can measure how well John does, or in general how well any algorithm does. First, we can check how well John does in the best case, or good scenarios, from the perspective of his strategy. In the range of 100 values, the answer being a low number like three at the start of the range is a good scenario; he can guess it fairly quickly. One is his best-case scenario. Or we could check how well he does on average. We could run this game a bunch of times and average out the running time. This would give us a much better picture of John's performance over time, but our estimates would be too high if the value he was searching for was at the start of the range, or far too low if it was at the end of the range. Let's imagine a scenario where Facebook naively implements linear search when finding friends. They looked at the latest U.S. census, saw that 50% of names start with the letters A through J, which is the first 40% of the alphabet, and thought, okay, on average linear search serves us well. But what about the rest of those whose names start with the letter after J in the alphabet? Searching for my name would take longer than the average, and much longer for someone whose name starts with the letter Z. So while measuring the run time of an algorithm on average might seem like a good strategy, it won't necessarily provide an accurate picture. By picking the maximum in the range, we're measuring how our algorithm does in the worst-case scenario. Analyzing the worst-case scenario is quite useful because it indicates that the algorithm will never perform worse than we expect; there's no room for surprises.

Back to our graph, we're going to plot the number of tries, a proxy for running time of the algorithm, against the number of values in the range, which will shorten to n. n here also represents John's worst-case scenario. When n is 10, he takes 10 turns; when n is 100, he takes 100 turns. But these two values alone are insufficient to really get any sort of visual understanding. Moreover, it's not realistic; John may take a long time to work through 100 numbers, but a computer can do that in no time. To evaluate the performance of linear search in the context of a computer, we should probably throw some harder and larger ranges of values at it. The nice thing is, by evaluating a worst-case scenario, we don't actually have to do that work; we know what the result will be. For a given value of n using linear search, it will take n tries to find the value in the worst-case scenario. So let's add a few values in here to build out this graph.

Okay, so we have a good picture of what this is starting to look like. As the values get really large, the running time of the algorithm gets large as well. We sort of already knew that. Before we dig into this runtime any deeper, let's switch tracks and evaluate Brittany's work. By having something to compare against, it should become easier to build a mental model around time complexity. The algorithm John used, linear search, seemed familiar to us, and you could understand it because it's how most of us search for things in real life anyway. Brittany's approach, on the other hand, got results quickly, but it was a bit harder to understand. So let's break it down.

Just like John's approach, Brittany started with a series of values, or a list of numbers, as her input. Where John just started at the beginning of the list and searched sequentially, Brittany's strategy is to always start in the middle of the range. From there, she asks a comparison question: Is the number in the middle of the range equal to the answer she's looking for? And if it's not, is it greater than or less than the answer? If it's greater than, she can eliminate all the values less than the one she's currently evaluating. If it's lesser than the answer, she can eliminate all the values greater than the one she's currently evaluating. With the range of values that she's left over with, she repeats this process until she arrives at the answer.

Let's visualize how she did this by looking at round three. In round three, the number of values in the range was 100; the answer was 5. The bar here represents the range of values, one on the left, 100 at the right, and this pointer represents the value Brittany chooses to evaluate. So she starts in the middle at 50. She asks, "Is it equal to the answer?" I say it's too high. So this tells her that the value she is evaluating is greater than our target value, which means there's no point in searching any of the values to the right of 50, that is, values greater than 50 in this range, so she can discard those values altogether. She only has to consider values from 1 to 50. Now the beauty of this strategy, and the reason why Brittany was able to find the answer in such few turns, is that with every value she evaluates, she can discard half of the current range. On her second turn, she picks the value in the middle of the current range, which is 25. She asks the same question; I say that the value is too high again, and this tells her that she can discard everything greater than 25, and the range of values drops from 1 to 25. Again, she evaluates the number in the middle, roughly, so that'd be 13 here. I tell her this is still too high. She discards the values greater, moves to value at 7, which is still too high, then she moves to 4, which is now too low. She can discard everything less than 4, which leaves the numbers 4 through 7. Here she picked 6, which was too high, which only leaves one value, 5. This seems like a lot of work, but being able to get rid of half the values with each turn is what makes this algorithm much more efficient.

Now there's one subtlety to using binary search, and you might have caught on to this. For this search method to work, as we've mentioned, the values need to be sorted. With linear search, it doesn't matter if the values are sorted, since a linear search algorithm just progresses sequentially, checking every element in the list. If the target value exists in the list, it will be found. But let's say this range of values, 100, was unsorted. Brittany would start at the middle with something like 14 and ask if this value was too low or too high. I say it's too high, so she discards everything less than 14. Now this example starts to fall apart here because, well, Brittany knows what numbers are less than 14 and greater than one; she doesn't need an actual range of values to solve this. A computer, however, does need that. Remember, search algorithms are run against lists containing all sorts of data; it's not always just a range of values containing numbers. In a real use case of binary search, which we're going to implement in a bit, the algorithm wouldn't return the target value because we already know that it's a search algorithm, so we're providing something to search for. Instead, what it returns is the position in the list that the target occupies. Without the list being sorted, a binary search algorithm would discard all the values to the left of 14, which over here could include the position where our target value is. Eventually, we'd get a result back saying the target value doesn't exist in the list, which is inaccurate. Earlier, when defining linear simple search, I said that the input was a list of values and the output was the target value, or more specifically, the position of the target value in the list. So with binary search, there's also that precondition: the input list must be sorted.

So let's formally define binary search: first, the input: a sorted list of values; the output: the position in the list of the target value we're searching for, or some sort of value indicating that the target does not exist in the list. Remember our guidelines for defining an algorithm; let me put those up again really quick: the steps in the algorithm need to be in a specific order; the steps also need to be very distinct; the algorithms should produce a result; and finally, the algorithm should complete in a finite amount of time. Let's use those to define this algorithm: Step one: We determine the middle position of the sorted list. Step two: We compare the element in the middle position to the target element. Step three: If the elements match, we return the middle position and end. If they don't match, in step four, we check whether the element in the middle position is smaller than the target element. If it is, then we go back to step two with a new list that goes from the middle position of the current list to the end of the current list. In step five, if the element in the middle position is greater than the target element, then again we go back to step two with a new list that goes from the start of the current list to the middle position of the current list. We repeat this process until the target element is found or until a sublist contains only one element. If that single-element sublist does not match the target element, then we end the algorithm, indicating that the element does not exist in the list.

Okay, so that is the magic behind how Brittany managed to solve the round much faster. In the next video, let's talk about the efficiency of binary search. [Music]

We have a vague understanding that Brittany's approach is better in most cases, but just like with linear search, it helps to visualize this. Much like we did with linear search when determining the efficiency of an algorithm, and remember we're still only looking at efficiency in terms of time, time complexity as it's called, we always want to evaluate how the algorithm performs in the worst-case scenario. Now you might be thinking, well, that doesn't seem fair because, given a series of data, if the target value we're searching for is somewhere near the front of the list, then linear search may perform just as well, if not slightly better than binary search, and that is totally true. Remember, a crucial part of learning algorithms is understanding what works better in a given context. When measuring efficiency, though, we always use the worst-case scenarios as a benchmark because, remember, it can never perform worse than the worst case. Let's plot these values on the graph we started earlier, with the number of tries, or the runtime of the algorithm, on the y-axis, and the maximum number of values in the series, or n, on the horizontal axis. To represent the worst-case scenario, we have two data points: when n equals 10, Brittany took four tries using binary search, and when n equals 100, it took seven tries. But even side by side, these data points are sort of meaningless. Remember that while there is quite a difference between the runtime of linear search and binary search at an n value of 100, for a computer that shouldn't matter. What we should check out is how the algorithm performs at levels of n that might actually slow a computer down. As n grows larger and larger, how do these algorithms compare to one another? Let's add that to the graph.

Okay, now a picture starts to emerge. As n gets really large, the performance of these two algorithms differs significantly. The difference is kind of staggering, actually. Even with the simple game, we saw that binary search was better, but now we have a much more complete idea of how much better. For example, when n is 1000, the runtime of linear search, measured by the number of operations or turns, is also 1000. For binary search, it takes just 10 operations. Now let's look at what happens when we increase n by a factor of 10. At 10,000, linear search takes 10,000 operations, while binary search takes 14 operations. An increase by a factor of 10 in binary search only needs four more operations to find a value. If we increase it again by a factor of 10 once more, to an n value of 100,000, binary search takes only 17 operations; it is blazing fast. What we've done here is plotted on a graph how the algorithm performs as the input set it is working on increases. In other words, we've plotted the growth rate of the algorithm, also known as the order of growth. Different algorithms grow at different rates, and by evaluating their growth rates, we get a much better picture of their performance because we know how the algorithm will hold up as n grows larger. This is so important, in fact, it is the standard way of evaluating an algorithm and brings us to a concept called Big O. You might have heard this word thrown about, and if you found it confusing, don't worry; we've already built up a definition in the past few videos; we just need to bring it all together.

Let's start with a common statement you'll see in studies on algorithms: Big O is a theoretical definition of the complexity of an algorithm as a function of the size. Wow, what a mouthful! This sounds really intimidating, but it's really not. Let's break it down. Big O is a notation used to describe complexity, and what I mean by notation is that it simplifies everything we've talked about down into a single variable. An example of complexity written in terms of Big O looks like this: O(n). As you can see, it starts with an uppercase letter O; that's why we call it Big O; it's literally a big O. The O comes from order of magnitude of complexity, so that's where we get the Big O from. Now complexity here refers to the exercise we've been carrying out in measuring efficiency. If it takes Brittany 4 tries when n is 10, how long does the algorithm take when n is 10 million? When we use Big O for this, the variable used, which we'll get to, distills that information down so that by reading the variable you get a big-picture view without having to run through data points and graphs just like we did. It's important to remember that complexity is relative. When we evaluate the complexity of the binary search algorithm, we're doing it relative to other search algorithms; not all algorithms. Big O is a useful notation for understanding both time and space complexity, but only when comparing amongst algorithms that solve the same problem. The last bit in that definition of Big O is a function of the size, and all this means is that Big O measures complexity as the input size grows, because it's not important to understand how an algorithm performs in a single data set, but in all possible data sets. You will also see Big O referred to as the upper bound of the algorithm, and what that means is that Big O measures how the algorithm performs in the worst-case scenario. So that's all Big O is; nothing special; it's just a notation that condenses the data points and graphs that we've built up down to one variable.

Okay, so what do these variables look like? For John's strategy, linear search, we say that it has a time complexity of Big O(n). So that's again Big O with an n inside parentheses. For Brittany's strategy, binary search, we say that it has a time complexity of Big O(log n). That's Big O with something called a log and an n inside parentheses. Now don't worry if you don't understand that; we'll go into that in more detail later on in the course. Each of these has a special meaning.

But it helps to work through all of them to get a big picture view. So, over the next few videos, let's examine what are called common complexities, or common values of Big O, that you will run into and should internalize.

In our discussions of complexity, we made one assumption: that the algorithm as a whole had a single measure of complexity. That isn't true, and we'll get at how we arrive at these measures for the entire algorithm at the end of this exercise. But each step in the algorithm has its own space and time complexity. In linear search, for example, there are multiple steps, and the algorithm goes like this: Start at the beginning of the list or range of values. Compare the current value to the target. If the current value is the target value that we're looking for, we're done. If it's not, we'll move on sequentially to the next value in the list and repeat step two. If we reach the end of the list, then the target value is not in the list.

Let's go back to step two for a second: Comparing the current value to the target. Does the size of the data set matter for this step? When we're at step two, we're already at that position in the list, and all we're doing is reading the value to make a comparison. Reading the value is a single operation, and if we were to plot it on a graph of runtime per operations against n, it looks like this: a straight line that takes constant time regardless of the size of n. Since this takes the same amount of time in any given case, we say that the run time is constant time; it doesn't change. In Big O notation, we represent this as Big O with a 1 inside parentheses.

Now, when I first started learning all this, I was really confused as to how to read this, even if it was in my own head. Should I say "Big O of one"? When you see this written, you're going to read this as constant time. So, reading a value in a list is a constant-time operation. This is the most ideal case when it comes to run times because input size does not matter, and we know that regardless of the size of n, the algorithm runtime will remain the same.

The next step up in complexity, so to speak, is the situation we encountered with the binary search algorithm. Traditionally, explaining the time complexity of binary search involves math. I'm going to try to do it both with and without. When we played the game using binary search, we noticed that with every turn we were able to discard half of the data. But there's another pattern that emerges that we didn't explore. Let's say n equals 10. How long does it take to find an item at the 10th position of the list? We can write this out: so we go from 10 to 5 to 8 to 9 and then down to 10. Here, it takes us four tries to cut down the list to just one element and find the value we're looking for. Let's double the value of n to 20 and see how long it takes for us to find an item at the 20th position. So we start at 20, and then we pick 10; from there we go to 15, 17, 19, and finally 20. So here it takes us five tries. Okay, let's double it again so that n is 40, and we try to find the item in the 40th position. So when we start at 40, the first midpoint we're going to pick is 20; from there we go to 30, then 35, 37, 39, and then 40. Notice that every time we double the value of n, the number of operations it takes to reduce the list down to a single element only increases by 1.

There's a mathematical relationship to this pattern, and it's called a logarithm of n. You don't really have to know what logarithms truly are, but I know that some of you like underlying explainers, so I'll give you a quick one. If you've taken algebra classes, you may have learned about exponents. Here's a quick refresher: 2 times 1 equals 2. Now, this can be written as 2 raised to the first power because it is our base case; two times one is two. Now, two times two is four. This can be written as two raised to the second power because we're multiplying two twice: first we multiply two times one, then the result of that times 2. 2 times 2 times 2 is 8, and we can write this as 2 raised to the 3rd power because we're multiplying 2 three times. In 2 raised to 2 and 2 raised to 3, the 2 and 3 there are called exponents, and they define how the number grows. With 2 raised to 3, we start with the base value and multiply itself 3 times. The inverse of an exponent is called a logarithm. So if I say log to the base 2 of 8 equals 3, I'm basically saying the opposite of an exponent. Instead of saying, "How many times do I have to multiply this value?" I'm asking, "How many times do I have to divide 8 by two to get the value one?" This takes three operations. What about the result of log to the base two of sixteen? That evaluates to four.

So why does any of this matter? Notice that this is sort of how binary search works: log to the base 2 of 16 is 4. If n was 16, how many triads does it take to get to that last element? Well, we start in the middle at 8; that's too low, so we move to 12, then we move to 14, then to 15, and then to 16, which is 5 tries, or log to the base 2 of 16 plus 1. In general, for a given value of n, the number of tries it takes to find the worst-case scenario is log of n plus one. And because this pattern is overall a logarithmic pattern, we say that the runtime of such algorithms is logarithmic. If we plot these data points on our graph, a logarithmic runtime looks like this. In Big O notation, we represent a logarithmic runtime as Big O of log n, which is written as Big O with log n inside parentheses, or even sometimes as ln n inside parentheses. When you see this, read it as logarithmic time. As you can see on the graph, as n grows really large, the number of operations grows very slowly and eventually flattens out. Since this line is below the line for a linear runtime, which we'll look at in a second, you might often hear algorithms with logarithmic runtimes being called sublinear. Logarithmic, or sub-linear, runtimes are preferred to linear because they're more efficient. But in practice, linear search has its own set of advantages, which we'll take a look at in the next video.

Next up, let's look at the situation we encountered with the linear search algorithm. We saw that in the worst-case scenario, whatever the value of n was, John took exactly that many tries to find the answer. As in linear search, when the number of operations to determine the result in the worst-case scenario is at most the same as n, we say that the algorithm runs in linear time. We represent this as Big O of n. Now you can read that as Big O of n, like I just said, or you can say linear time, which is more common. When we put that up on a graph against constant time and logarithmic time, we get a line that looks like this. Any algorithm that sequentially reads the input will have linear time. So remember, anytime you know a problem involves reading every item in a list, that means a linear run time. As you saw from the game we played, Brittany's strategy using binary search was clearly better, and we can see that on the graph. So if we had the option, why would we use linear search, which runs in linear time? Remember that binary search had a precondition: the input set had to be sorted. While we won't be looking at sorting algorithms in this course, as you learn more about algorithms, you'll find that sorting algorithms have varying complexities themselves, just like search does. So we have to do additional work prior to using binary search. For this reason, in practice, linear search ends up being more performant up to a certain value of n because the combination of sorting first and then searching using binary search adds up.

The next common complexity you will hear about is when an algorithm runs in quadratic time. If the word quadratic sounds familiar to you, it's because you might have heard about it in math class. Quadratic is a word that means an operation raised to the second power, or when something is squared. Let's say you and your friends are playing a tower defense game, and to start it off, you're going to draw a map of the terrain. This map is going to be a grid, and you pick a random number to determine how large this grid is. Let's set n, the size of the grid, to four. Next, you need to come up with a list of coordinates so you can place towers and enemies and stuff on this map. So how would we do this? If we start out horizontally, we'd have coordinate points that go 1, 1, 1, 2, 1, 3, and 1, 4. Then you go up one level vertically, and we have points 2, 1, 2, 2, 2, 3, and 2, 4. Go up one more, and you have the points 3, 1, 3, 2, 3, 3, and 3, 4. And on that last row, you have the points 4, 1, 4, 2, 4, 3, and 4, 4. Notice that we have a pattern here: for each row, we take the value and then create a point by adding to that every column value. The range of values go from 1 to the value of n. So we can generally think of it this way: for the range of values from 1 to n, for each value in that range, we create a point by combining that value with the range of values from 1 to n again. Doing it this way, for each value in the range of 1 to n, we create an n number of values, and we end up with 16 points, which is also n times n, or n squared. This is an algorithm with a quadratic runtime because for any given value of n, we carry out n squared number of operations. Now, I picked a relatively easy, so to speak, example here because, in English at least, we often denote map sizes by height times width, so we would call this a 4 by 4 grid, which is just another way of saying 4 squared, or n squared. In Big O notation, we would write this as Big O of n squared, or say that this is an algorithm with a quadratic runtime. Many search algorithms have a worst-case quadratic runtime, which you'll learn about soon.

Now, in addition to quadratic runtimes, you may also run into cubic runtimes as you encounter different algorithms. In such an algorithm, for a given value of n, the algorithm executes n raised to the third power number of operations. These aren't as common as quadratic algorithms, though, so we won't look at any examples, but I think it's worth mentioning. Thrown up on our graph, quadratic and cubic runtimes look like this. So this is starting to look pretty expensive computationally, as they say. We can see here that for small changes in n, there's a pretty significant change in the number of operations that we need to carry out.

The next worst-case runtime we're going to look at is one that's called quasi-linear, and a sort of easier to understand, for lack of better word, by starting with the Big O notation. Quasi-linear runtimes are written out as Big O of n times log n. We learned what log n was, right? A logarithmic runtime. Whereas n grew, the number of operations only increased by a small factor. With a quasi-linear runtime, what we're saying is that for every value of n, we're going to execute a log n number of operations; hence the runtime of n times log n. So you saw earlier with the quadratic runtime that for each value of n, we conducted n operations. It's sort of the same in that as we go through the range of values in n, we're executing log n operations. In comparison to other runtimes, a quasi-linear algorithm has a runtime that lies somewhere between a linear runtime and a quadratic runtime. So where would we expect to see this kind of runtime in practical use? Well, sorting algorithms is one place you will definitely see it. Merge sort, for example, is a sorting algorithm that has a worst-case runtime of Big O of n log n. Let's take a look at a quick example. Let's say we start off with a list of numbers that looks like this, and we need to sort it. Merge sort starts by splitting this list into two lists down the middle. It then takes each sub-list and splits that in half down the middle again. It keeps doing this until we end up with a list of just a single number. When we're down to single numbers, we can do one sort operation and merge these sub-lists back in the opposite direction. The first part of merge sort cuts those lists into sub-lists with half the numbers. This is similar to binary search, where each comparison operation cuts down the range to half the values. You know the worst-case runtime in binary search is log n, so these splitting operations have the same runtime: Big O of log n, or logarithmic. But splitting into half isn't the only thing we need to do with merge sort; we also need to carry out comparison operations so we can sort those values. And if you look at each step of this algorithm, we carry out an n number of comparison operations, and that brings the worst-case runtime of this algorithm to n times log n, also known as quasi-linear. Don't worry if you didn't understand how merge sort works; that wasn't the point of this demonstration. We will be covering merge sorts soon in a future course.

The run times we've looked at so far are all called polynomial runtimes. An algorithm is considered to have a polynomial runtime if, for a given value of n, its worst-case runtime is in the form of n raised to the k power, where k just means some value. So it could be n squared, where k equals 2 for a quadratic runtime, n cubed for a cubic runtime, and so on. All of those are in the form of n raised to some power. Anything that is bounded by this—and what I mean by that is if we had a hypothetical line on our graph of n raised to the k power—anything that falls under this graph is considered to have a polynomial runtime. Algorithms with an upper bound, or a runtime with a Big O value that is polynomial, are considered efficient algorithms and are likely to be used in practice.

Now, the next class of runtimes that we're going to look at are runtimes that we don't consider efficient, and these are called exponential runtimes. With these runtimes, as n increases slightly, the number of operations increases exponentially, and as we'll see in a second, these algorithms are far too expensive to be used. An exponential runtime is an algorithm with a Big O value of some number raised to the nth power. Imagine that you wanted to break into a locker that had a padlock on it. Let's assume you forgot your code. This lock takes a two-digit code, and the digit for the code ranges from zero to nine. You start by setting the dials to zero, and then, with the first dial remaining on zero, you change the second dial to one and try and open it. If it doesn't work, you set it to two, then try again. You would keep doing this, and if you still haven't succeeded with the second dial set to 9, then you go back to that first dial, set it to 1, and start the second dial over. The range of values you'd have to go through is 0, 0 to 9, 9, which is 100 values. This can be generalized as 10 to the second power, since there are 10 values on each dial raised to two dials. Searching through each individual value until you stumble on the right one is a strategy called brute force, and brute force algorithms have exponential run times. Here, there are two dials, so n is 2, and each dial has 10 values, so again we can generalize this algorithm as 10 raised to n, where n represents the number of dials. The reason that this algorithm is so inefficient is because with just one more dial on the lock, the number of operations increases significantly. With three dials, the number of combinations in the worst-case scenario, where the correct code is the last digit in the range, is 10 raised to 3, or 1,000 values. With an additional wheel, it becomes 10 raised to 4, or 10,000 values. As n increases, the number of operations increases exponentially to a point where it's unsolvable in a realistic amount of time.

Now you might think, "Well, any computer can crack a four-digit numerical lock," and that's true because n here is sufficiently small. But this is the same principle that we use for passwords. In a typical password field implemented well, users are allowed to use letters of the English alphabet, so up to 26 characters, numbers from 0 to 9, and a set of special characters, of which there can be around 33. So typically, that means each character in a password can be one out of 69 values. This means that for a one-character password, it takes 69 to the nth power, so 1, which equals 69 operations in the worst-case scenario to figure out the password. Just increasing n to 2 increases the number of operations needed to guess the password to 69 squared, or 4,761 operations. Now, usually on a secure website, there isn't really a limit, but in general, passwords are limited to around 20 characters in length. With each character being a possible 69 values and there being 20 characters, the number of operations needed to guess the password in the worst-case scenario is 69 raised to the 20th power, or approximately 6 followed by 36 zeros—number of operations. An Intel CPU with five cores can carry out roughly about 65,000 million instructions per second. That's a funny number, I know. To crack our 20-digit passcode in this very simplistic model, it would take this Intel CPU 6 raised to the 20th power years to brute force the password. So while this algorithm would eventually produce a result, it is so inefficient that it's pointless. This is one of the reasons why people recommend you have longer passwords, since brute forcing is exponential in the worst case; each character you add increases the number of combinations by an exponent.

The next class of exponential algorithms is best highlighted by a popular problem known as the traveling salesman. The problem statement goes like this: Given a list of cities and the distance between each pair of cities, what is the shortest possible route that visits each city and then returns to the origin city? This seems like a simple question, but let's start with a simple case: three cities, A, B, and C. To figure out what the shortest route is, we need to come up with all the possible routes. With three cities, we have six routes. In theory, at least, some of these routes can be discarded because ABC is the same as CBA, but in the opposite direction. But as we do know, sometimes going from A to C through B may go through a different route than C to A through B, so we'll stick to the six routes. And from there, we could determine the shortest—no big deal. Now, if we increase this to four cities, we jump to 24 combinations. The mathematical relationship that defines this is called a factorial and is written out as n followed by an exclamation point. Factorials are basically n times n minus one, repeated until you reach the number one. So, for example, the factorial of three is three times two times one, which is six, which is the number of combinations we came up with for three cities. The factorial of four is four times three times two times one, or 24, which is the number of combinations we arrived at with four cities. In solving the traveling salesman problem, the most efficient algorithm will have a factorial runtime, or a combinatorial runtime, as it's also called. At low values of n, algorithms with a factorial runtime may be used, but with an n value of, say, 200, it would take longer than humans have been alive to solve the problem. For sake of completeness, let's plot a combinatorial runtime on our graph so that we can compare an algorithm such as one that solves the traveling salesman problem, as a worst-case runtime of Big O of n factorial. Studying exponential runtimes like this are useful for two reasons: First, in studying how to make such algorithms efficient, we develop strategies that are useful across the board and can potentially be used to make existing algorithms even more efficient. Second, it's important to be aware of problems that take a long time to solve. Knowing right off the bat that a problem is somewhat unsolvable in a realistic time means you can focus your efforts on…

other aspects of the problem as beginners, though we're going to steer clear of all this and focus our efforts on algorithms with polynomial runtimes. Since we're much more likely to work with and learn about such algorithms now that we know some of the common complexities. In the next video, let's talk about how we determine the complexity of an algorithm, because there are some nuances.

Over the last few videos, we took a look at common complexities that we would encounter in studying algorithms, but the question remains: how do we determine what the worst-case complexity of an algorithm is? Earlier, I mentioned that even though we say that an algorithm has a particular upper bound or worst-case runtime, each step in a given algorithm can have different run times. Let's bring up the steps for binary search again. Assuming the list is sorted, the first step is to determine the middle position of the list. In general, this is going to be a constant-time operation. Many programming languages hold on to information about the size of the list, so we don't actually need to walk through the list to determine the size. Now, if we didn't have information about the size of the list, we would need to walk through counting each item one by one until we reached the end of the list, and this is a linear-time operation. But realistically, this is a Big O of 1, or constant-time, step.

Step 2 is to compare the element in the middle position to the target element. We can assume that in most modern programming languages this is also a constant-time operation because the documentation for the language tells us it is. Step 3 is our success case, and the algorithm ends. This is our best case, and so far we have only incurred two constant-time operations, so we would say that the best-case run time of binary search is constant time, which is actually true. But remember that best case is not a useful metric. Step 4: if we don't match, is splitting the list into sub-lists. Assuming the worst-case scenario, the algorithm would keep splitting into sub-lists until a single-element list is reached with the value that we're searching for. The run time for this step is logarithmic since we discard half the values each time.

So in our algorithm, we have a couple steps that are constant time and one step that is logarithmic. Overall, when evaluating the run time for an algorithm, we say that the algorithm has as its upper bound the same runtime as the least efficient step in the algorithm. Think of it this way: let's say you're participating in a triathlon, which is a race that has a swimming, running, and a cycling component. You could be a phenomenal swimmer and a really good cyclist, but you're a pretty terrible runner. No matter how fast you are at swimming or cycling, your overall race time is going to be impacted the most by your running race time, because that's the part that takes you the longest. If you take an hour 30 to finish the running component, 55 minutes to swim, and 38 minutes to bike, it won't matter if you can fine-tune your swimming technique down to finish in 48 minutes and your cycle time to 35, because you're still bounded at the top by your running time, which is close to almost double your bike time. Similarly, with the binary search algorithm, it doesn't matter how fast we make the other steps; they're already as fast as they can be. In the worst-case scenario, the splitting of the list down to a single-element list is what will impact the overall running time of your algorithm. This is why we say that the time complexity or run time of the algorithm in the worst case is Big O of log n, or logarithmic.

As I alluded to, though, your algorithm may hit a best-case runtime, and in between the two—best and worst case—have an average run time as well. This is important to understand because algorithms don't always hit their worst case, but this is getting a bit too complex for us for now. We can safely ignore average-case performances and focus only on the worst case. In the future, if you decide to stick around, we'll circle back and talk about this more. Now that you know about algorithms complexities and Big O, let's take a break from all of that and write code. In the next video [Music]

So far, we've spent a lot of time in theory, and while these things are all important things to know, you get a much better understanding of how algorithms work when you start writing some code. As I mentioned earlier, we're going to be writing Python code in this and all subsequent algorithm courses. If you do have programming experience but in another language, check the notes section of this video for an implementation in your language. If you don't have any experience, I'll try my best to explain as we go along. On the video you're watching right now, you should see a Launch Workspaces button. We're going to use a Treehouse coding environment called Workspaces to write all of our code. If you're familiar with using Python in a local environment, then feel free to keep doing so. Workspaces is an in-browser coding environment and will take care of all the setup and installation so you can focus on just writing and evaluating code. Workspaces is quite straightforward to use. On the left here, we have a file navigator pane, which is currently empty since we haven't created a new file. On the top, we have an editor where we write all our code, and then below that we have a terminal or a command-line prompt where we can execute the scripts that we write. Let's add a new file here, so at the top in the editor area, we're going to go to File, New File, and we'll name this linear_search.py.

In here, we're going to define our linear search algorithm as a standalone function. We start with the keyword `def`, which defines a function or a block of code, and then we give it the name `linear_search`. This function will accept two arguments: first, the list we're searching through, and then the target value we're looking for. Both of these arguments are enclosed in a set of parentheses, and there's no space between the name of the function and the arguments. After that, we have a colon. Now there might be a bit of confusion here since we already have this target value—what are we searching for? Unlike the game we played at the beginning where John's job was to find the value, in a true implementation of linear search, we're looking for the position in the list where the value exists. If the target is in the list, then we return its position, and since this is a list, that position is going to be denoted by an index value. Now, if the target is not found, we're going to return `None`. The choice of what to return in the failure case may be different in other implementations of linear search. You can return -1, since that isn't typically an index value. You can also raise an exception, which is Python speak for indicating an error occurred. Now I think for us the most straightforward value we can return here is `None`.

Now let's add a comment to clarify this. So hit Enter to go to the next line, and then we're going to add three single quotes, and then below that on the next line we'll say: `Returns the position or the index position of the target if found, else returns None`, and then on the next line we'll close off those three quotes. This is called a docstring and is a Python convention for documenting your code. The linear search algorithm is a sequential algorithm that compares each item in the list until the target is found. To iterate or loop or walk through our list sequentially, we're going to use a `for` loop. Now typically when iterating over a list in Python, we would use a loop like this: we'd say `for item in list`. This assigns the value at each index position to that local variable `item`. We don't want this though, since we primarily care about the index position. Instead, we're going to use the `range` function in Python to create a range of values that start at 0 and end at the number of items in the list. So we'll say `for i`—`i` stands for index here—`in range`, starting at 0 and going all the way up to the length of the list. We can get the number of items in the list using the `len` function. Now going back to our talk on complexity and how individual steps in an algorithm can have its own run times, this is a line of code that we would have to be careful about. Python keeps track of the length of a list, so this function call here, `len(list)`, is a constant-time operation. Now if this were a naive implementation, let's say we wrote the implementation of the list and we iterate over the list every time we call this length function, then we've already incurred a linear cost. Okay, so once we have a range of values that represent index positions in this list, we're going to iterate over that using the `for` loop and assign each index value to this local variable `i`. Using this index value, we can obtain the item at that position using subscript notation on the list. Now this is also a constant-time operation because the language says so. So we'll do: `if list[i]`. Once we have this value, which we'll get by using subscript notation, so we'll say `list[i]`, once we have this value we'll check if it matches the target. So `if list[i] == target`. Well, if it does, then we'll return that index value because we want the position, and once we hit this `return` statement, we're going to terminate our function. If the entire `for` loop is executed and we don't hit this `return` statement, then the target does not exist in the list. So at the bottom here we'll say `return None`.

Even though all the individual operations in our algorithm run in constant time, in the worst-case scenario, this `for` loop here will have to go through the entire range of values and read every single element in the list, therefore giving the algorithm a Big O value of n, or running in linear time. Now if you've written code before, you've definitely written code like this a number of times, and I bet you didn't know, but all along you are implementing what is essentially a well-known algorithm. So I hope this goes to show you that algorithms are a pretty approachable topic. Like everything else, this does get advanced, but as long as you take things slow, there's no reason for it to be impossible. Remember that not any block of code counts as an algorithm. To be a proper implementation of linear search, this block of code must return a value, must complete execution in a finite amount of time, and must output the same result every time for a given input set. So let's verify this with a small test. Let's write a function called `verify` that accepts an index value. If the value is not `None`, it prints the index position; if it is `None`, it informs us that the target was not found in the list. So `def verify(index):`, and this is going to take an index value, and we'll say: `if index is not None:` then we'll print `Target found at index:`, `index`, `else:` that needs to go back there, we go, `else:` we'll say `Target not found in list`. Okay, using this function, let's define a range of numbers now. So this will be a list `numbers`, and we'll just go from 1 to, let's say, 10. Now if you've written Python code before, you know that I can use a list comprehension to make this easier, but we'll keep things simple. We can now use our `linear_search` function to search for the position of a target value in this list. So we can say `result = linear_search(numbers, 12)`, and then we'll `verify(result)`. If our algorithm works correctly, the `verify` function should inform us that the target did not exist. So make sure you save the file, which you can do by going up to File and Save or hitting Command-S. And then below in the terminal, you're going to type out `python linear_search.py`, or you can hit Tab and it should autocomplete `linear_search.py`. As you can see, correct, the target was not found in the list. So the output of our script is what we expect. For our second test, let's search for the value 6 in the list. So you can copy this command, C to copy, and then paste it again, and we'll just change 12 here to 6, and then come back down to the terminal, hit the up arrow to execute the same command again, and hit Enter. You'll notice that I forgot to hit Save, so it did not account for that new change. We'll try that again, and there you'll see that if it works correctly, which it did, the index should be number 5. Run the program on your end and make sure everything works as expected. Our algorithm returned a result in each case; it executed in a finite time, and the results were the ones we expect. In the next video, let's tackle binary search.

In the last video, we left off with an implementation of linear search. Let's do the same for binary search so that we get an understanding of how this is represented in code. So we'll do this in a new file. Back to File, New File, and we'll name this one `binary_search.py`. Like before, we're going to start with a function named `binary_search`. So we'll say `def binary_search(list, target):`. If you remember, binary search works by breaking the array or list down into smaller sets until we find the value we're looking for. We need a way to keep track of the position of the list that we're working with, so let's create two variables, `first` and `last`, to point to the beginning and end of the array. So `first = 0`. Now, if you're new to programming, list positions are represented by index values that start at 0 instead of 1. So here we're setting `first` to 0 to point to the first element in the list. `last` is going to point to the last element in the list, so we'll say `last = len(list) - 1`. Now this may be confusing to you, so a quick sidebar to explain what's going on. Let's say we have a list containing 5 elements. If we called `len` on that list, we should get 5 back because there are 5 elements, but remember that because the position numbers start at 0, the last value is not at position 5 but at 4. In nearly all programming languages, getting the position of the last element in the list is obtained by determining the length of the list and deducting 1, which is what we're doing. Okay, so we know what the first and last positions are when we start the algorithm. For our next line of code, we're going to create a `while` loop. A `while` loop takes a condition and keeps executing the code inside the loop until the condition evaluates to false. For our condition, we're going to say to keep executing this loop until the value of `first` is less than or equal to the value of `last`. So `while first <= last:` Well, why you ask? Why is this our condition? Well, let's work through this implementation, and then a visualization should help.

Inside the `while` loop, we're going to calculate the midpoint of our list, since that's the first step of binary search. `midpoint = first + last // 2`. Now the two forward slashes here are what Python calls a floor division operator. What it does is it rounds down to the nearest whole number. So if we have an eight-element array, `first` is 0, `last` is 7; if we divided 0 + 7, which is 7, by 2, we would get 3.5. Now 3.5 is not a valid index position, so we round that down to 3 using the floor division operator. Okay, so now we have a midpoint. The next step of binary search is to evaluate whether the value at this midpoint is the same as the target we're looking for. So say `if list[midpoint] == target:` Well, if it is, then we'll go ahead and return the midpoint. So we'll say `return midpoint`. The `return` statement terminates our algorithm, and over here we're done. This is our best-case scenario. Next we'll say `else if list[midpoint] < target:` Now here, if the value is less—the value at `midpoint` is less than the target—then we don't care about any of the values lower than the midpoint, so we redefine `first` to point to the value after the midpoint. So we'll say `midpoint + 1`. Now if the value at the midpoint is greater than the target, then we can discard the values after the midpoint and redefine `last` to point to the value prior to the midpoint. So we'll say `else: last = midpoint - 1`. Let's visualize this. We're going to start with a list of nine integers. To make this easier to understand, let's specify these integers to be of the same value as its index position, so we have a range of values from 0 to 8. Our target is the worst-case scenario; we're looking for the position of the value 8. At the start, our algorithm sets `first` to point to the index 0 and `last` to point to the length of the list minus 1, which is 8. Next we hit our `while` loop. The logic of this loop is going to be executed as long as the value of `first` is not greater than the value of `last`, or as we've defined it, we're going to keep executing the contents of the loop as long as `first` is less than or equal to `last`. On the first pass, this is true, so we enter the body of the loop. The midpoint is `first + last` divided by 2 and rounded down, so we get a nice even 4. The value at this position is 4. Now this is not equal to the target, so we move to the first `else if`. 4 is less than 8, so now we redefine `first` to point to `midpoint + 1`, which is 5. `first` is still less than `last`, so we run through the body of the loop again. The midpoint is now 6. 6 is less than 8, so we move `first` to point to 7. 7 is still less than or equal to 8, so we go for another iteration of the loop. The midpoint is 7, oddly enough, and 7 is still less than the target, so we move `first` to point to 8. `first` is equal to `last` now, but our condition says keep the loop going as long as `first` is less than or equal to `last`, so this is our final time through the loop. The midpoint is now 8, which makes the value at the midpoint equal to the target, and we finally exit our algorithm and return the position of the target. Now what if we had executed all this code and never hit a case where `midpoint == target`? Well, that would mean the list did not contain the target value. So after the `while` loop, at the bottom, will `return None`.

We have several operations that make up our binary search algorithm, so let's look at the runtime of each step. We start by assigning values to `first` and `last`. The value assigned to `last` involves a call to the `len` function to get the size of the list, but we already know this is a constant-time operation in Python, so both of these operations run in constant time. Inside the loop, we have another value assignment, and this is a simple division operation, so again the runtime is constant. In the next line of code, we're reading a value from the list and comparing the midpoint to the target; both of these again are constant-time operations. The remainder of the code is just a series of comparisons and value assignments, and we know that these are all constant-time operations as well. So if all we have are a series of constant-time operations, why does this algorithm have, in the worst case, a logarithmic runtime? It's hard to evaluate by just looking at the code, but the `while` loop is what causes the run time to grow. Even though all we're doing is a comparison operation, by redefining `first` and `last` over here, or rather in the last two steps over here, we're asking the algorithm to run as many times as it needs until `first` is equal to or greater than `last`. Now each time the loop does this, the size of the data set—the size of the list—grows smaller by a certain factor until it approaches a single element, which is what results in the logarithmic runtime. Okay, just like with linear search, let's test that our algorithm works. So we'll go back to `linear_search.py`, and we're going to copy-paste, so Command-C to copy, if you're on a

Mac, then go back to binary search and at the bottom, oops, we're going to paste in that verify function. Okay, we'll also go back and grab this numbers. You know what, let's go ahead and copy all, all of these things, so numbers and the two verify cases. We'll paste that in as well, and the only thing we need to change here is instead of calling linear search, this is going to call binary search. Okay, we'll hit command s to save the file, and then I'm going to drag up my console and we'll run python binary search.py and hit enter, and you'll see, like just like before, we get the same results back.

Now, note that an extremely important distinction needs to be made here: the numbers list that we've defined for our test cases, right here, has to be sorted. The basic logic of binary search relies on the fact that if the target is greater than the midpoint, then our potential values lie to the left, or vice versa. Since the values are sorted in ascending order, if the values are unsorted, our implementation of binary search may return none even if the value exists in the list.

And just like that, you've written code to implement two search algorithms. How fun was that? Hopefully this course has shown you that it isn't a topic to be afraid of, and that algorithms, like any other topic with code, can be broken down and understood piece by piece.

Now we have a working implementation of binary search, but there's actually more than one way to write it. So in the next video, let's write a second version. I'm going to create a new file, as always, File, New File, and we'll name this recursive_binary_search.py. Okay, so we're going to add our new implementation here, so that we don't get rid of that first implementation we wrote. Let's call this new function recursive_binary_search. Unlike our previous implementation, this version is going to behave slightly differently in that it won't return the index value of the target element if it exists; instead, it will just return a true value if it exists and a false if it doesn't.

So recursive_binary_search, and like before, this is going to take a list; it accepts a list and a target to look for in that list. We'll start the body of the function by considering what happens if an empty list is passed in. In that case, we would return false. So I would say, if the length of the list, which is one way to figure out if it's empty, if it's equal to zero, then we'll return false.

Now you might be thinking that in the previous version of binary search we didn't care if the list was empty. Well, we actually did, but in a roundabout sort of way. So in the previous version of binary search, our function had a loop, and that loop condition was true when first was less than or equal to last. So as long as it's less than or equal to last, we continue the loop. Now if we have an empty list, then first is greater than last, and the loop would never execute, and we return none at the bottom. So this is the same logic we're implementing here; we're just doing it in a slightly different way. If the list is not empty, we'll implement an else clause. Now here we'll calculate the midpoint by dividing the length of the list by 2 and rounding down. Again, there's no use of first and last here, so we'll say length of list, and then using the floor division operator, we'll divide that by 2. If the value at the midpoint, which we'll check by saying if list, using subscript notation, we'll say midpoint as the index. Now if this value at the midpoint is the same as the target, then we'll go ahead and return true. So far this is more or less the same, except for the value that we're returning. Let me actually get rid of all that. Okay, all right. So if this isn't the case, let's implement an else clause.

Now here we have two situations. So first, if the value at the midpoint is less than the target, so if value at midpoint is less than the target, then we're going to do something new: we're going to call this function again, this recursive_binary_search function that we're in the process of defining. We're going to call that again, and we're going to give it the portion of the list that we want to focus on. In the previous version of binary search, we moved the first value to point to the value after the midpoint. Now here we're going to create a new list using what is called a slice operation and create a sub list that starts at midpoint plus 1 and goes all the way to the end. We're going to specify the same target as a search target, and when this function call is done we'll return the value. So we'll say return the return is important. Then we'll call this function again, recursive_binary_search, and this function takes a list, and here we're going to use that subscript notation to perform a slice operation by using two indexes, a start and an end. So we'll say our new list that we're passing in needs to start at midpoint plus 1, and then we'll go all the way to the end. This is a Python syntactic sugar, so to speak; if I don't specify an end index, Python knows to just go all the way to the end. All right, so this is our new list that we're working with, and we need a target; we'll just pass it through. If you're confused, bear with me; just like before, we'll visualize this at the end. Okay, we have another else case here, and this is a scenario where the value at the midpoint is greater than the target, which means we only care about the values in the list from the start going up to the midpoint. Now in this case as well, we're going to call the binary search function again and specify a new list to work with. This time the list is going to start at the beginning and then go all the way up to the midpoint. So it looks the same; we'll say return recursive_binary_search. We're going to pass in a list here, so if we just put a colon here without a start index, Python knows to start at the beginning, and we're going to go all the way up to the midpoint. The target here is the same, and this is our new binary search function. So let's see if this works. Actually, yes. Down here we'll make some space and we'll define a verify function. We're not going to copy paste the previous one because we're not returning none or an integer here, so we'll verify the result that we pass in and we'll say print target found, and this is just going to say true or false whether we found it. Okay, so like before, we need a numbers list, and we'll do something: one, two, three, four, all the way up to eight. Okay, and now let's test this out. So we'll call our recursive_binary_search function and we'll pass in the numbers list, and the target here is 12. We're going to verify this, verify the result, make sure it works, and then we'll call it again, this time making sure that we give it a target that is actually in the list. So here we'll say 6, and we'll verify this again. Make sure you hit command s to save, and then in the console below we're going to type out python recursive_binary_search.py, run it, and you'll see that we've verified that search works. While we can't verify the index position of the target value, which is a modification to how our algorithm works, we can guarantee by running across all valid inputs that search works as intended.

So why write a different search algorithm here, a different binary search algorithm, and what's the difference between these two implementations anyway? The difference lies in these last four lines of code that you see here. We did something unusual here. Now before we get into this, a small word of advice: this is a confusing topic, and people get confused by it all the time. Don't worry; that doesn't make you any less of a programmer. In fact, I have trouble with it often and always look it up, including when I made this video. This version of binary search is a recursive binary search. A recursive function is one that calls itself. This is hard for people to grasp sometimes because there are few easy analogies that make sense, but you can think of it and sort this way.

So let's say you have this book that contains answers to multiplication problems. You're working on a problem, and you look up an answer in the book. The answer for your problem says, "Add 10 to the answer for problem 52." Okay, so you look up problem 52, and there it says, "Add 12 to the answer for problem 85." Well, then you go and look up the answer to problem 85, and finally, instead of redirecting you somewhere else, that answer says 10. So you take that 10, and then you go back to problem 52, because remember the answer for problem 52 was to add 12 to the answer for problem 85. So you take that 10, and then you now have the answer to problem 85, so you add 10 to 12 to get 22. Then you go back to your original problem where it said to add 10 to the answer for problem 52, so you add 10 to 22 and you get 32 to end up with your final answer. So that's a weird way of doing it, but this is an example of recursion. The solution to your first lookup in the book was the value obtained by another lookup in the same book, which was followed by yet another lookup in the same book. The book told you to check the book until you arrived at some base value. Our function works in a similar manner. So let's visualize this with an example of list. Like before, we have a nine-element list here with values zero through eight. The target we're searching for is the value eight. We'll check if the list is empty by calling len on it. This list is not empty, so we go to the else clause. Next we calculate the midpoint: 9 divided by 2 is 4.5, rounded down is 4. So our first midpoint value is 4. We'll perform our first check: is the value at the midpoint equal to the target? Not true, so we go to our else clause. We'll perform another check here: is the value at the midpoint less than the target? Now in our case this is true. Earlier when we evaluated this condition, we simply change the value of first. Here we're going to call the recursive_binary_search function again and give it a new list to work with. The list starts at midpoint plus 1, so at index position 5, all the way to the end. Notice that this call to recursive_binary_search inside of recursive_binary_search includes a return statement. This is important, and we'll come back to that in a second. So now we're back at the top of a new call to recursive_binary_search with effectively a new list, although technically just a sub list of the first one. The list here contains the numbers 6, 7, and 8. Starting with the first check, the list is not empty, so we move to the else. The midpoint in this case, length of the list 3 divided by 2 rounded down is 1. Is the value of the midpoint equal to the target? Well, the value at that position is 7, so no. In the else, we perform the first check: is the value at the midpoint less than the target? Indeed it is, so we call recursive_binary_search again and provided a new list. This list starts at midpoint plus 1 and goes to the end, so in this case that's a single-element list. Since this is a new call to recursive_binary_search, we start back up at the top. Is the list empty? No. The midpoint is zero. Is the value at the midpoint the same as the target? It is, so now we can return true. Remember a minute ago I pointed out that when we call recursive_binary_search from inside the function itself, it's preceded by a return statement. That plays a pretty important role here. So back to our visualization, we start at the top and recall binary search with a new list, but because that's got a return statement before it, what we're saying is, "Hey, when you run binary search on this, whatever value you get back, return it to the function that called you." Then at the second level we call binary search again, along with another return statement. Like with the first call, we're instructing the function to return a value back to the code that called it. At this level we find the target, so the function returns true back to the caller, but since this inner function was also called by a function with instructions to return, it keeps returning that true value back up until we reach the very first function that called it. Going back to our book of answers, recursive_binary_search instructs itself to keep working on the problem until it has a concrete answer. Once it does, it works its way backwards, giving the answer to every function that called it until the original caller has an answer. Now, like I said at the beginning, this is pretty complicated, so you should not be concerned if this doesn't click. Honestly, this is not one thing that you're going to walk away with knowing fully how to understand recursion after your first try. I'm really not lying when I say I have a pretty hard time with recursion.

Now before we move on, I do want to point out one thing: even though the implementation of recursion is harder to understand, it is easier in this case to understand how we arrive at the logarithmic run time since we keep calling the function with smaller lists. Let's take a break here. In the next video, let's talk a bit more about recursion and why it matters. [Music]

In the last video, we wrote a version of binary search that uses a concept called recursion. Recursion might be a new concept for you, so let's formalize how we use it. A recursive function is one that calls itself. In our example, the recursive_binary_search function called itself inside the body of the function. When writing a recursive function, you always need a stopping condition, and typically we start the body of the recursive function with this stopping condition. It's common to call this stopping condition the base case. In our recursive_binary_search function, we had two stopping conditions. The first was what the function should return if an empty list is passed in. It seems weird to evaluate an empty list because you wouldn't expect to run search on an empty list, but if you look at how our function works, recursive_binary_search keeps calling itself, and with each call to itself the size of the list is cut in half. If we searched for a target that didn't exist in the list, then the function would keep halving itself until it got to an empty list. Consider a three-element list with numbers one, two, three, where we're searching for a target of four. On the first pass, the midpoint is 2, so the function would call itself with the list 3. On the next pass, the midpoint is 0, and the target is still greater, so the function would call itself, this time passing in an empty list because an index of 0 plus 1 in a single-element list doesn't exist. When we have an empty list, this means that after searching through the list, the value wasn't found. This is why we define an empty list as a stopping condition or a base case that returns false. If it's not an empty list, then we have an entirely different set of instructions we want to execute. First, we obtain the midpoint of the list. Once we have the midpoint, we can introduce our next base case or stopping condition: if the value at the midpoint is the same as the target, then we return true. With these two stopping conditions, we've covered all possible paths of logic through the search algorithm: you can either find the value or you don't. Once you have the base cases, the rest of the implementation of the recursive function is to call the function on smaller sub-lists until we hit one of these base cases. Going back to our visualization for a second, we see that recursive_binary_search calls itself a first time, which then calls itself again. For the initial list we started with, the function only calls itself a few times before a stopping condition is reached. The number of times a recursive function calls itself is called recursive depth.

Now the reason I bring all of this up is because if, after you start learning about algorithms, you decide you want to go off and do your own research, you may start to see a lot of algorithms implemented using recursion. The way we implemented binary search the first time is called an iterative solution. Now when you see the word iterative, it generally means the solution was implemented using a loop structure of some kind. A recursive solution, on the other hand, is one that involves a set of stopping conditions and a function that calls itself. Computer scientists and computer science textbooks, particularly from back in the day, favor and are written in what are called functional languages. In functional languages, we try to avoid changing data that is given to a function. In our first version of binary search, we created first and last variables using the list and then modified first and last as we needed to arrive at a solution. Functional languages don't like to do this—all this modification of variables—and prefer a solution using recursion. A language like Python, which is what we're using, is the opposite and doesn't like recursion. In fact, Python has a maximum recursion depth after which our function will halt execution. Python prefers an iterative solution.

Now I mentioned all of this for two reasons. If you decide that you want to learn how to implement the algorithm in a language of your choice that's not Python, then you might see a recursive solution as the best implementation in that particular language. I'm an iOS developer, for example, and I work with a language called Swift. Swift is different from Python in that it doesn't care about recursion depth and does some neat tricks where it doesn't even matter how many times your function calls itself. So if you want to see this in Swift code, then you need to know how recursion works well, and now you have some idea.

Now the second reason I bring it up is actually way more important, and to find out, on to the next video. At the beginning of this series, I mentioned that there were two ways of measuring the efficiency of an algorithm. The first was time complexity, or how the run time of an algorithm grows as n grows larger. The second is space complexity. We took a pretty long route to build up this example, but now we're in a good place to discuss space complexity. Space complexity is a measure of how much working storage or extra storage is needed as a particular algorithm grows. We don't think about it much these days, but every single thing we do on a computer takes up space in memory. In the early days of computing, considering memory usage was of paramount importance because memory was limited and really expensive. These days we're spoiled; our devices are rich with memory. This is okay when we write everyday code because most of us aren't dealing with enormously large data sets. When we write algorithms, however, we need to think about this because we want to design our algorithms to perform as efficiently as it can as the size of the data set n grows really large. Like time complexity, space complexity is measured in the worst-case scenario using big-O notation. Since you are familiar with the different kinds of complexities, let's dive right into an example. In our iterative implementation of binary search—the first one we wrote that uses a while loop—let's look at what happens to our memory usage as n gets large. Let's bring up that function. Let's say we start off with a list of 10 elements. Now inspecting the code, we see that our solution relies heavily on these two variables, first and last. First points to the start of the list and last to the end. When we eliminate a set of values, we don't actually create a sub list; instead, we just redefine first and last, as you see here, to point to a different section of the list. Since the algorithm only considers the values between first and last when determining the midpoint, by redefining first and last as the algorithm proceeds, we can find a solution using just the original list. This means that for any value of n, the space complexity of the iterative version of binary search is constant, or that the iterative version of binary search takes constant space. Remember that we would write this as Big O of one. This might seem confusing because as n grows, we need more storage to account for that larger list size. Now this is true, but that storage is not what space complexity cares about measuring. We care about what additional storage is needed.

Needed as the algorithm runs and tries to find a solution. If we assume something simple, say that for a given size of a list represented by a value n, it takes n amount of space to store it, whatever that means. Then, for the iterative version of binary search, regardless of how large the list is at the start, middle, and end of the algorithm process, the amount of storage required does not get larger than n. And this is why we consider it to run in constant space.

Now, this is an entirely different story with the recursive version, however. In the recursive version of binary search, we don't make use of variables to keep track of which portion of the list we're working with. Instead, we create new lists every time with a subset of values, or sub-lists, with every recursive function call. Let's assume we have a list of size n, and in the worst-case scenario, the target element is the last in the list. Calling the recursive implementation of binary search on this list and target would lead to a scenario like this: the function would call itself and create a new list that goes from the midpoint to the end of the list. Since we're discarding half the values, the size of the sub-list is n/2. This function will keep calling itself, creating a new sub-list that's half the size of the current one until it arrives at a single-element list and a stopping condition.

This pattern that you see here, where the size of the sub-list is reduced by a factor on each execution of the algorithmic logic—well, we've seen that pattern before. Do you remember where? This is exactly how binary search works; it discards half the values every time until it finds a solution. Now we know that, because of this pattern, the running time of binary search is logarithmic. In fact, the space complexity of the recursive version of binary search is the same. If we start out with a memory allocation of size n that matches the list, on each function call of recursive binary search, we need to allocate additional memory of size n/2, n/4, and so on, until we have a sub-list that is either empty or contains a single value. Because of this, we say that the recursive version of the binary search algorithm runs in logarithmic time, with a Big O of log n.

Now there's an important caveat here: this totally depends on the language. Remember how I said that a programming language like Swift can do some tricks to where recursion depth doesn't matter? The same concept applies here. If you care to read more about this concept, it's called tail optimization. It's called tail optimization because, if you think of a function as having a head and a tail, if the recursive function call is the last line of code in the function, as it is in our case, we call this tail recursion since it's the last part of the function that calls itself. Now the trick that Swift does to reduce the amount of space and therefore computing overhead to keep track of these recursive calls is called tail call optimization or tail call elimination. It's one of those things that you'll see thrown around a lot in algorithm discussions, but may not always be relevant to you.

Now, what, if any, of this is relevant to us? Well, Python does not implement tail call optimization, so the recursive version of binary search takes logarithmic space. If we had to choose between the two implementations, given that the time complexity, or run time, of both versions—the iterative and the recursive version—are the same, we should definitely go with the iterative implementation in Python since it runs in constant space. Okay, that was a lot, but with all of this, we've now established two important ways to distinguish between algorithms that handle the same task and determine which one we should use. We've arrived at what I think is a good spot to take a long break and let all of these new concepts sink in. But before you go off to the next course, let's take a few minutes to recap everything we've learned so far.

While we did implement two algorithms in this course in actual code, much of what we learned here was conceptual and will serve as building blocks for everything we're going to learn in the future. So let's list all of it out. The first thing we learned about, and arguably the most important, was algorithmic thinking. Algorithmic thinking is an approach to problem-solving that involves breaking a problem down into a clearly defined input and output, along with a distinct set of steps that solves the problem by going from input to output. Algorithmic thinking is not something you develop overnight by taking one course, so don't worry if you're thinking, "I still don't truly know how to apply what I learned here." Algorithmic thinking sinks in after you go through several examples in a similar fashion to what we did today. It also helps to apply these concepts in the context of a real example, which is another thing we will strive to do moving forward. Regardless, it is important to keep in mind that the main goal here is not to learn how to implement a specific data structure or algorithm off the top of your head. I'll be honest, I had to look up a couple code snippets for a few of the algorithms myself in writing this course. But in going through this, you now know that binary search exists and can apply to a problem where you need a faster search algorithm. Unlike most courses where you can immediately apply what you have learned to build something cool, learning about algorithms and data structures will pay off more in the long run.

The second thing we learned about is how to define and implement algorithms. We've gone over these guidelines several times; I won't bore you here again at the end, but I will remind you that if you're often confused about how to effectively break down a problem in code to something more manageable, following those algorithm guidelines is a good place to start. Next, we learned about Big O and measuring the time complexity of algorithms. This is a mildly complicated topic, but once you've abstracted the math away, it isn't as hazy a topic as it seems. Now, don't get me wrong, the math is pretty important, but only for those designing and analyzing algorithms. Our goal is more about how to understand and evaluate algorithms. We learned about common run times like constant, linear, logarithmic, and quadratic runtimes. These are all fairly new concepts, but in time you will immediately be able to distinguish the runtime of an algorithm based on the code you write and have an understanding of where it sits on an efficiency scale. You will also, in due time, internalize runtimes of popular algorithms, like the fact that binary search runs in logarithmic time and constant space, and be able to recommend alternative algorithms for a given problem. All in all, over time the number of tools in your tool belt will increase.

Next, we learned about two important search algorithms and the situations in which we select one over the other. We also implemented these algorithms in code so that you got a chance to see them work. We did this in Python, but if you are more familiar with a different language and haven't gotten the chance to check out the code snippets we've provided, you should try your hand at implementing it yourself; it's a really good exercise to go through. Finally, we learned about an important concept and a way of writing algorithmic code through recursion. Recursion is a tricky thing, and depending on the language you write code with, you may run into it more than others. It is also good to be aware of because, as we saw in our implementation of binary search, whether recursion was used or not affected the amount of space we used. Don't worry if you don't fully understand how to write recursive functions; I don't truly know either. The good part is you can always look these things up and understand how other people do it. Anytime you encounter recursion in our courses moving forward, you'll get a full explanation of how and why the function is doing what it's doing. And that brings us to the end of this course. I'll stress again that the goal of this course was to get you prepared for learning about more specific algorithms by introducing you to some of the tools and concepts you will need moving forward. So if you're sitting there thinking, "I still don't know how to write many algorithms or how to use algorithmic thinking," that's okay; we'll get there. Just stick with it. As always, have fun and happy coding. [Music]

Hi, my name is Passant. I'm an instructor at Treehouse, and welcome to the Introduction to Data Structures course. In this course, we're going to answer one fundamental question: why do we need more data structures than a programming language provides? Before we answer that question, some housekeeping, if you will. In this course, we're going to rely on concepts we learned in the Introduction to Algorithms course, namely Big-O notation, space and time complexity, and recursion. If you're unfamiliar with those concepts or just need a refresher, check out the prerequisites courses listed. In addition, this course does assume that you have some programming experience. We're going to use data structures that come built into nearly all programming languages as our point of reference. While we will explain the basics of how these structures work, we won't be going over how to use them in practice. If you're looking to learn how to program before digging into this content, check the notes section of this video for helpful links. If you're good to go, then awesome. Let's start with an overview of this course.

The first thing we're going to do is to explore a data structure we are somewhat already familiar with: arrays. If you've written code before, there's a high chance you have used an array. In this course, we're going to spend some time understanding how arrays work, what are the common operations on an array, and what are the run times associated with those operations. Once we've done that, we're going to build a data type of our own called a linked list. In doing so, we're going to learn that there's more than one way to store data; in fact, there's way more than just one way. We're also going to explore what motivates us to build specific kinds of structures and look at the pros and cons of these structures. We'll do that by exploring four common operations: accessing a value, searching for a value, inserting a value, and deleting a value. After that, we're actually going to circle back to algorithms and implement a new one, a sorting algorithm. In the Introductions to Algorithms course, we implemented a binary search algorithm; a precondition to binary search was that the list needed to be sorted. We're going to try our hand at sorting a list and open the door to an entirely new category of algorithms. We're going to implement our sorting algorithm on two different data structures and explore how the implementation of one algorithm can differ based on the data structure being used. We'll also look at how the choice of data structure potentially influences the run time of the algorithm. In learning about sorting, we're also going to encounter another general concept of algorithmic thinking called divide and conquer, along with recursion. Divide and conquer will be a fundamental tool that we will use to solve complex problems, all in due time. In the next video, let's talk about arrays.

A common data structure built into nearly every programming language is the array. Arrays are a fundamental data structure and can be used to represent a collection of values, but it is much more than that. Arrays are also used as building blocks to create even more custom data types and structures. In fact, in most programming languages, text is represented using the string type, and under the hood, strings are just a bunch of characters stored in a particular order in an array. Before we go further and dig into arrays, what exactly is a data structure? A data structure is a way of storing data when programming. It's not just a collection of values and the format they're stored in, but the relationship between the values in the collection as well as the operations applied on the data stored in the structure. An array is one of very many data structures. In general, an array is a data structure that stores a collection of values where each value is referenced using an index or a key. A common analogy for thinking about arrays is as a set of train cars; each car has a number, and these cars are ordered sequentially. Inside each car, the array, or the train in this analogy, stores some data. While this is the general representation of an array, it can differ slightly from one language to another, but for the most part, all these fundamentals remain the same. In a language like Swift or Java, arrays are homogeneous containers, which means they can only contain values of the same type. If you use an array to store integers in Java, it can only store integers. In other languages, arrays are heterogeneous structures that can store any kind of value. In Python, for example, you can mix numbers and text with no issues. Now, regardless of this nuance, the fundamental concept of an array is the index. This index value is used for every operation on the array, from accessing values to inserting, updating, and deleting.

In Python, the language we're going to be using for this course, it's a tiny bit confusing: the type that we generally refer to as an array in most languages is best represented by the list type in Python. Python does have a type called array as well, but it's something different, so we're not going to use it. While Python calls it a list, when we use a list in this course, we'll be talking about concepts that apply to arrays as well in other languages, so definitely don't skip any of this. There's one more thing: in computer science, a list is actually a different data structure than an array, and in fact, we're going to build a list later on in this course. Generally, though, this structure is called a linked list as opposed to just list, so hopefully the terminology isn't too confusing. To properly understand how arrays work, let's take a peek at how arrays are stored under the hood. An array is a contiguous data structure. This means that the array is stored in blocks of memory that are right beside each other, with no gaps. The advantage of doing this is that retrieving values is very easy. In a non-contiguous data structure—we're going to build one soon—the structure stores a value as well as a reference to where the next value is. To retrieve that next value, the language has to follow that reference, also called a pointer, to the next block of memory. This adds some overhead, which, as you will see, increases the runtime of common operations.

A second ago, I mentioned that depending on the language, arrays can either be homogeneous, containing the same type of value, or heterogeneous, where any kind of value can be mixed. This choice also affects the memory layout of the array. For example, in a language like C, Swift, or Java, where arrays are homogeneous, when an array is created, since the kind of value is known to the language compiler—and you can think of the compiler as the brains behind the language—it can choose a contiguous block of memory that fits the array size and values created. If the values were integers, assuming an integer took up space represented by one of these blocks, then for a five-item array, the compiler can allocate five blocks of equally sized memory. In Python, however, this is not the case; we can put any value in a Python list; there's no restriction. The way this works is a combination of contiguous memory and the pointers or references I mentioned earlier. When we create a list in Python, there is no information about what will go into that array, which makes it hard to allocate contiguous memory of the same size. There are several advantages to having contiguous memory: since the values are stored beside each other, accessing the values happens in almost constant time, so this is a characteristic we want to preserve. The way Python gets around this is by allocating contiguous memory and storing in it not the value we want to store, but a reference or a pointer to the value that's stored somewhere else in memory. By doing this, it can allocate equally sized contiguous memory, since regardless of the value size, the size of the pointer to that value is always going to be equal. This incurs an additional cost in that when a value is accessed, we need to follow the pointer to the block of memory where the value is actually stored, but Python has ways of dealing with these costs that are outside the scope of this course.

Now that we know how an array stores its values, let's look at common operations that we execute on an array. Regardless of the kind of data structure you work with, all data structures are expected to carry out four kinds of operations at minimum: we need to be able to access and read values stored in the structure; we need to be able to search for an arbitrary value; we also need to be able to insert a value at any point into the structure; and finally, we need to be able to delete structures. Let's look at how these operations are implemented on the array structure in some detail, starting with access. Elements in an array are identified using a value known as an index, and we use this index to access and read the value. Most programming languages follow a zero-based numbering system when it comes to arrays, and all this means is that the first index value is equal to zero, not one. Generally speaking, when an array is declared, a base amount of contiguous memory is allocated as the array storage. Computers refer to memory through the use of an address, but instead of keeping a reference to all the memory allocated for an array, the array only has to store the address of the first location because the memory is contiguous. Using the base address, the array can calculate the address of any value by using the index position of that value as an offset. If you want to be more specific, think of it this way: let's say we want to create an array of integers, and then each integer takes up a certain amount of space in memory that we'll call m. Let's also assume that we know how many elements we're going to create, so the size of the array is some number of elements we'll call n. The total amount of space that we need to allocate is n times the space per item m. If the array keeps track of the location in memory where the first value is held—so let's label that m0—then it has all the information it needs to find any other element in the list. When accessing a value in an array, we use the index to get the first element in the list; we use the zeroth index; to get the second, we use the index value 1, and so on. Given that the array knows how much storage is needed for each element, it can get the address of any element by starting off with the address for the first element and adding to that the index value times the amount of storage per element. For example, to access the second value, we can start with m0 and to that add m times the index value 1, giving us m1 as the location in memory for the second address. This is a very simplified model, but that's more or less how it works. This is only possible because we know that array memory is contiguous, with no gaps.

Let's switch over to some code. As I mentioned earlier, we're going to be using Python in this course. If you don't know how to code, or you're interested in this content but know a language other than Python, check the notes section of this video for more information. While the code will be in Python, the concepts are universal and, more importantly, simple enough that you should have no issue following along in your favorite programming language. And to get started, click on the Launch Workspaces button on the video page that you're watching right now. This should spin up an instance of a Treehouse workspace, an in-browser coding environment. Right now, your workspace should be empty, and that's expected, so let's add a new file in here. I'm going to go to File, New File, and we'll call this arrays.py. Creating a list in Python is quite simple, so we'll call this new_list. We use a set of square brackets around a set of values to create a list, so one, and we comma-separate them, so space two and space three. This allocates a base amount of memory for the array to use, or when I say array, know that in Python I mean a list, since this is Python. The values aren't stored in memory; instead, the values 1, 2, and 3 are stored elsewhere in memory, and the array stores references to each of those objects. To access a value, we use a subscript along with an index value, so to get the first value we use the index 0, and if we were to assign this to another variable, we would say result equals new_list. We write out new_list since this is

The array that we're accessing the value from and then a subscript notation, which is a square bracket, and then the index value, as we saw. Since the array has a reference to the base location in memory, the position of any element can be determined pretty easily. We don't have to iterate over the entire list; all we need to do is a simple calculation of an offset from the base memory. Since we're guaranteed that the memory is contiguous, for this reason, access is a constant time operation on an array or a Python list. This is also why an array crashes if you try to access a value using an index that is out of bounds of what the array stores.

If you've used an array before, you've undoubtedly run into an error or a crash where you try to access a value using an index that was larger than the number of elements in the array. Since the array calculates the memory address on the fly when you access a value with an out-of-bounds index, as it's called, the memory address returned is not one that's part of the array structure and therefore cannot be read by the array. Now, in Python, this is represented by an IndexError, and we can make this happen by using an index we know our array won't contain.

Now I'm writing out my code here inside of a text editor, which obviously doesn't run the code, so let's drag up this console area here, and I'm going to write Python to bring up the Python interpreter. In here we can do the same thing, so I can say new_list = 1, 2, 3. And now this is an interpreter, so it's actually going to evaluate our code. All right, so now we have a new_list. If I type out new_list, it gets printed out into the console. Okay, I can also do new_list[0], and you'll see that I get the value 1, which is the value stored at the zeroth index. Now, to highlight that IndexError, we can do new_list, and inside the square brackets we can provide an index that we know our array doesn't contain. So here I'll say index 10, and if I hit Enter, you'll see it say IndexError: list index out of range. And those are the basics of how we create and read values from an array.

In the next video, let's take a look at searching. In the last video, we learned what happens under the hood when we create an array and read a value using an index. In this video, we're going to look at how the remaining data structure operations work on arrays. If you took the introduction to algorithms course, we spent time learning about two search algorithms: linear search and binary search. While arrays are really fast at accessing values, they're pretty bad at searching. Taking an array as is, the best we can do is use linear search for a worst-case linear runtime. Linear search works by accessing and reading each value in the list until the element in concern is found. If the element we're looking for is at the end of the list, then every single element in the list will have been accessed and compared. Even though accessing and comparing are constant-time operations, having to do this for every element results in an overall linear time.

Let's look at how search works in code. In Python, we can search for an item in an array in one of two ways. We can use the `in` operator to check whether a list contains an item. So I can say `if 1 in new_list: print(True)`. The `in` operator actually calls a `contains` method that is defined on the list type, which runs a linear search operation. In addition to this, we can also use a `for` loop to iterate over the list manually and perform a comparison operation. So I can say: `for n in new_list: if n == 1: print(True); break`. This is more or less the implementation of linear search. If the array were sorted, however, we could use binary search, but because sort operations incur a cost of their own, languages usually stay away from sorting the list and running binary search, since for smaller arrays, linear search on its own may be faster. Now again, remember that since this is an editor, this is just a text file; none of these lines of code are evaluated, so you can try that out in here. So we'll copy that; we can come down here and say Python, and hit Enter, and then when it starts up we can paste in our list, and now we can try what we just did. So `if 1 in new_list: print(True)`, and there you go, it prints True.

Now, because we've already learned about linear and binary search in a previous course, there's nothing new going on here. What's more interesting to look at, in my opinion, is inserting and deleting values in an array. Let's start with inserting. In general, most array implementations support three types of insert operations. The first is a true insert using an index value, where we can insert an element anywhere in the list. This operation has a linear runtime. Imagine you wanted to insert an item at the start of the list. When we insert into the first position, what happens to the item that is currently in that spot? Well, it has to move to the next spot at index value one. What happens to the second item at index position one? That one moves to the next spot at index position two. This keeps happening until all elements have been shifted forward one index position. So, in the worst-case scenario, inserting at the zeroth position of an array, every single item in the array has to be shifted forward, and we know that any operation that involves iterating through every single value means a linear runtime.

Now, the second way we can insert an item into an array is by appending. Appending, although technically an insert operation in that it inserts an item into an existing array, doesn't incur the same runtime cost because appends simply add the item to the end of the list. We can simplify and say that this is constant time. This is a constant-time operation, but it depends on the language implementation of array. To highlight why that matters, let's consider how lists in Python work. In Python, when we create a list, the list doesn't know anything about the size of the list and how many elements we're going to store. Creating a new empty list like so: `numbers = []`. So this creates a list and allocates a space of size n + 1. Since n here is zero, there are no elements in this array. In this list, space is allocated for a one-element list to start off. Because the space allocated for the list and the space used by the list are not the same, what do you think happens when we ask Python for the length of this list? So I can say `len(numbers)`. We correctly get 0 back. This means that the list doesn't use the memory allocation as an indicator of its size because, as I mentioned, it has allocated space for a one-element list, but it returns zero, so it determines it in other ways. Okay, so `numbers`, this list currently has space for one element. Let's use the `append` method defined on the type to insert a number at the end of the list. So you can say `numbers.append(2)`. Now the memory allocation and the size of the list are the same since the list contains one element. Now what if I were to do something like this: `numbers.append(200)`. Now, since the list only has an allocation for one item at this point, before it can add the new element to the list, it needs to increase the memory allocation and thereby the size of the list. It does this by calling a list resize operation. List resizing is quite interesting because it shows the ingenuity in solving problems like this. Python doesn't resize the list to accommodate just the element we want to add; instead, in this case, it would allocate four blocks of memory to increase the size to a total of four contiguous blocks of memory. It does this so that it doesn't have to resize the list every single time we add an element, but at very specific points. The growth pattern of the list type in Python is 0, 4, 8, 16, 25, 35, 46, and so on. This means that as the list size approaches these specific values, resize is called again. If you look at when the size of the list is four, this means that when appending four more values until the size of eight, each of those append operations do not increase the amount of space taken. At specific points, however, when resizing is triggered, space required increases as memory allocation increases. This might signify that the append method has a non-constant space complexity, but it turns out that because some operations don't increase space and others do, when you average all of them out, append operations take constant space. We say that it has an amortized constant space complexity. This also happens with insert operations. If we had a four-element array, we would have four elements and a memory allocation of four. An insert operation at that point doesn't matter where it happens on the list, but at that point it would trigger a resize. Inserting is still more expensive though because after the resize every element needs to be shifted over one.

The last insert operation that is supported in most languages is the ability to add one list to another. In Python, this is called an `extend` and looks like this. So I'll say `numbers`. Now if you let me actually clear out the console... oh actually you will... let's exit Python. We'll clear this out, so we're back at the top and we'll start again. So I'll say `numbers = []`, and now we can say `numbers.extend([4, 5, 6])`. And then once I hit Enter, if I were to print out `numbers`, you'll see that it now contains the values 4, 5, and 6. So `extend` takes another list to add. `extend` effectively makes a series of append calls on each of the elements in the new list until all of them have been appended to the original list. This operation has a runtime of O(k), where k represents the number of elements in the list that we're adding to our existing list.

The last type of operation we need to consider are delete operations. Deletes are similar to inserts in that when a delete operation occurs, the list needs to maintain correct index values. So where an insert shifts every element to the right, a delete operation shifts every element to the left. Just like an insert as well, if we delete the first element in the list, every single element in the list needs to be shifted to the left. Delete operations have an upper bound of O(n), also known as a linear runtime. Now that we've seen how common operations work on a data structure that we're quite familiar with, let's switch tracks and build our own data structure. [Music]

Over the next few videos, we're going to build a data structure that you may have worked with before: a linked list. Before we get into what a linked list is, let's talk about why we build data structures instead of just using the ones that come built into our languages. Each data structure solves a particular problem. We just went over the basics of the array data structure and looked at the cost of common operations that we carry out on arrays. We found that arrays were particularly good at accessing—reading values happens in constant time—but arrays are pretty bad at inserting and deleting, both of which run in linear time. Linked lists, on the other hand, are somewhat better at this, although there are some caveats. And if we're trying to solve a problem that involves far more inserts and deletes than accessing, a linked list can be a better tool than an array.

So what is a linked list? A linked list is a linear data structure where each element in the list is contained in a separate object called a node. A node models two pieces of information: an individual item of the data we want to store and a reference to the next node in the list. The first node in the linked list is called the head of the list, while the last node is called the tail. The head and the tail nodes are special; the list only maintains a reference to the head, although in some implementations it keeps a reference to the tail as well. This aspect of linked lists is very important, and as you'll see, most of the operations on the list need to be implemented quite differently compared to an array. The opposite of the head, the tail denotes the end of the list. Every node other than the tail points to the next node in the list, but tail doesn't point to anything. This is basically how we know it's the end of the list. Nodes are what are called self-referential objects; the definition of a node includes a link to another node, and self-referential here means the definition of node includes the node itself. Linked lists often come in two forms: a singly linked list, where each node stores a reference to the next node in the list, or a doubly linked list, where each node stores a reference to both the node before and after. If an array is a train with a bunch of cars in order, then a linked list is like a treasure hunt. When you start the hunt, you have a piece of paper with the location of the first treasure. You go to that location, and you find an item along with a location to the next item of treasure. When you finally find an item that doesn't also include a location, you know that the hunt has ended.

Now that we have a high-level view of what a linked list is, let's jump into code and build one together. We'll focus on building a singly linked list for this course. There are advantages to having a doubly linked list, but we don't want to get ahead of ourselves. Let's start here by creating a new file. We're going to put all our code for our linked list, so we'll call this `linked_list.py`. First, we're going to create a class to represent a node: `class Node:`. Now `Node` is a simple object in that it won't model much. So first we'll add a data variable; it's an instance variable here called `data`, and we'll assign the value `None` initially. And then we'll add one more; we'll call this `next_node`, and to this we'll assign `None` as well. So we've created two instance variables: `data` to hold on to the data that we're storing and `next_node` to point to the next node in the list. Now we need to add a constructor to make this class easy to create, so we'll add an `__init__` method here that takes `self` and some `data` to start off, and all we're going to do is assign `data` to that instance variable we created. So that's all we need to model `Node`. Before we do anything else though, let's document this. So right after the class definition, let's create a docstring: `"""An object for storing a single node of a linked list. Models two attributes: data and the link to the next node in the list."""`. Okay. Using the `Node` class is fairly straightforward, so we can create a new instance of `Node` with some data to store. Now the way we're going to do this is we're going to bring up the console, and we're going to type out like we've been typing out before: `python`, followed by the name of the script that we wrote, which is `linked_list.py`. But before we do that, we're going to pass an argument to the Python command; we're going to say `-i`, `python -i linked_list.py`. So what this does is this is going to run the Python REPL, the read-evaluate-print loop, in the console, but it's going to load the contents of our file into that so that we can use it. So I'll hit Enter, and we have a new instance going, and now we can use the `Node` in here. So we can say `n1 = Node(10)`. Now, if we try to inspect this object, the representation returned isn't very useful, which will make things really hard to debug as our code grows. So, for example, if I type out `n1`, you'll see that we have a valid instance here, but it's not very helpful the way it's printed out. So we can customize this by adding a representation of the object using the `__repr__` function. Now, in the terminal still, we'll type out `exit()`, like that, hit Enter to exit the console, and then down here let's add in some room. Okay, and here we'll say `def __repr__(self): return f"Node({self.data})"`. Okay, let's hit save, and before we move on, let's verify that this works. So I'm going to come in here, type `clear` to get rid of everything, and then we'll do what we did again, and you can just hit the up arrow a couple times to get that command. All right, so hit Enter, and now just so you know, every time you run this, you start off, you know, from scratch, so `n1` that we created earlier, not there anymore. So let's go ahead and create it: `n1 = Node(10)`, and we can type `n1` again and hit Enter, and you have a much better representation now. So we can see that we have a `Node`, and it contains the data 10. We can also create another one: `n2 = Node(20)`, and now we can say `n1.next_node = n2`. So `n1` now points to `n2`, and if we say `n1.next_node`, you'll see that it points to that node, the node containing 20. Nodes are the building blocks for a list, and now that we have a `Node` object, we can use it to create a singly linked list. So again, I'm going to exit out of this and then go back to the text editor, and here we'll create a new class: `class LinkedList:`. The `LinkedList` class is going to define a `head`, and this attribute models the only node that the list is going to have a reference to. So here we'll say `head = None`, and then like we did earlier, let's create a constructor: `__init__(self): self.head = None`. This is the same as doing this, so we can actually get rid of that and just use the constructor. Okay, so again, this `head` attribute models the only node that the list will have a reference to. Since every node points to the next node, to find a particular node, we can go from one node to the next in a process called list traversal. So in the class constructor here, we've set the default value of `head` to `None`, so that new lists created are always empty. Again, you'll notice here that I didn't explicitly declare the `head` attribute at the top of the class definition, and don't worry, that's not an oversight; the `self.head` in the initializer means that it's still created. Okay, so that's all there is to modeling a linked list. Now we can add methods that make it easier to use this data structure. First, a really simple docstring to provide some information: `"""Singly linked list."""`. A common operation carried out on data structures is checking whether it contains any data or whether it's empty. At the moment, to check if a list is empty, we would need to query these instance variables `head` and so on every time. Ideally, we would like to not expose the inner workings of our data structure to code that uses it. Instead, let's make this operation more explicit by defining a method: `def is_empty(self): return self.head is None`. All we're doing here is checking to see if `head` is `None`. If it is...

This condition evaluates to true, which indicates the list is empty. Now, before we end this video, let's add one more convenience method to calculate the size of our list. The name convenience method indicates that what this method is doing is not providing any additional functionality that our data structure can't handle right now, but instead making existing functionality easier to use. We could calculate the size of our linked list by traversing it every time using a loop until we hit a tail node, but doing that every time is a hassle. Okay, so we'll call this method `size`, and as always, it takes `self`. Unlike calling `len` on a Python list—not to be confused with a linked list—which is a constant time operation, our `size` operation is going to run in linear time. The only way we can count how many items we have is to visit each node and call `next` until we hit the tail node. So we'll start by getting a reference to the head. We'll say `current = self.head`. Let's also define a local variable named `count` with an initial value of 0 that will increment every time we visit a node. Once we hit the tail, `count` will reflect the size of that list.

Next, we'll define a `while` loop that will keep going until there are no more nodes. So say `while current`. `while current` is the same as writing out `while current != None`, but it's more succinct, so we'll go with this former. If the latter is more precise for you, you can go with that. Now, inside this loop, we'll increment the `count` value. So `count += 1`. `+=` if you haven't encountered it before, is the same as writing `count = count + 1`. So if `count` is zero initially, so it's `0 + 1 = 1`, and then we'll assign that back to `count`. Okay, so `count += 1`. Next, we're going to assign the next node in the list to `current`. So `current = current.nextNode`. This way, once we get to the tail and call `nextNode`, `current` will equal `None`, and the `while` loop terminates. So the end, we can return `count`. As you can see, we need to visit every node to determine the size, meaning our algorithm runs in linear time. So let's document this up in our docstring, which we'll add now to `size`. We'll say `"""Returns the number of nodes in the list. Takes linear time."""` Let's take a break here. We can now create lists, check if they're empty, and check the size. In the next video, let's start implementing some common operations. At the moment, we can create an empty list, but nothing else.

Let's define a method to add data to our list. Technically speaking, there are three ways we can add data to a list: we can add nodes at the head of the list, which means that the most recent node we created will be the head and the first node we created will be the tail; or we could flip that around—most recent nodes are the tail of the list, and the first node to be added is the head. I mentioned that one of the advantages of linked lists over arrays is that inserting data into the list is much more efficient than to the array. This is only true if we're inserting at the head or the tail. Technically speaking, this isn't an insert, and you'll often see this method called `add`, `prepend` if the data is added to the head, or `append` if it's added to the tail. A true insert is where you can insert the data at any point in the list, which is our third way of adding data. We're going to circle back on that. If we wanted to insert at the tail, then the list needs a reference to the tail node; otherwise, we would have to start at the head and walk down the length of the list, or traverse it, to find the tail. Since our list only keeps a reference to the head, we're going to add new items at the head of the list.

Now, before we add our new method, I forgot that I didn't show you in the last video how to actually use the code we just added and how to check every time, you know, when we add new code that it works correctly. So, like before, we're gonna bring up the console, and here we're gonna say `python -i linked_list.py`, which should load it—load the contents of our file—and now we'll start here by creating a linked list. So `l = LinkedList()`, and then we'll use a node. So `n1 = Node(10)`, and now we can assign `n1` to the nodes or to the linked list's head attribute. So `l1.head = n1`, and then we can see if `size` works correctly. So if we call `l1.size()`, and since this is a method, we need a set of parentheses at the end, and enter, you'll see that we get back `1` correctly. Okay, so it works. Now let's add our new method, which we're going to call `add`. `add` is going to accept some data to add to the list inside of a node. So we'll say `def add(self, data):`. First, we'll create a new node to hold on to the data. So `new_node = Node(data)`. Before we set the new node as the head of the list, we need to point the new node's `next` property at whatever node is currently at `head`. This way, when we set the new node as the head of the list, we don't lose a reference to the old head. So `new_node.nextNode = self.head`. Now, if there was no node at `head`, this correctly sets `nextNode` to `None`. Now we can set the new node as the head of the node. So say `self.head = new_node`. Because the insert operation is simply a reassignment of the `head` and `nextNode` properties, this is a constant time operation. So let's add that in as a docstring first—what the method does. So it adds a new node containing data at the head of the list. This operation takes constant time, which is our best-case scenario.

Okay, let's test this out. So I'm going to bring the console back up. We'll exit out of our current reply, and we'll load the contents of the file again. And now we don't need to create a node like we did earlier, so we can say `l = LinkedList()`. `l.add(1)`. Okay, let's see if this works. We'll call `size()`, and if it worked, the linked list should now have a size of one. There we go. You can also do `l.add(2)`, `l.add(3)`, and `l.size()` should now be three. There we go. Now, if we—I were to type `l` and just hit print again, what we get in the REPL is nothing useful. So, like before, we'll implement the wrapper function for our linked list. Now, I'm just going to copy-paste this in, and we'll walk through it. Okay, so this is what our implementation of `wrapper` looks like for the linked list object. You can grab this code from the notes section of this video. Okay, so at the top you'll see a docstring where it says it returns a string representation of the list, and like everything we need to do with a linked list, we need to traverse it, so this is going to take linear time. We start by creating an empty list. Now, I need to distinguish—this is a Python list, not a linked list—so we create an empty list called `nodes`, and two nodes, we're going to add strings that have a description that provide a description of each node, but we're not going to use the description that we implemented in the `Node` class because we're going to customize it a bit here. Next, we start by assigning `self.head` to `current`, so we sort of have a pointer to the head node. As long as `current` does not equal `None`, which means we're not at the tail, we're going to implement some logic. So in the first scenario, if the node assigned to `current` is the same as the head, then we're going to append this string to our `nodes` list, and the string is simply going to say that, hey, this is a head node, and it contains some data, which will extract using `current.data`. Next scenario is if the node assigned to `current`'s `nextNode` is `None`, meaning we're at the tail node, then we'll assign a different kind of string. So it's the same as earlier, except we're saying `tail` here, and then finally, in any other scenario, which means we're not at the head or not of the tail, we'll simply print the node's value inside, and again, we'll extract it using `current.data`. With every iteration of the loop, we'll move `current` forward by calling `current.nextNode` and reassigning it, and then at the very end, when we're done, we'll join all the strings that are inside the `nodes` list together using the Python `join` method, and we'll say that with every join—so when you join these two strings together to make one string, you need to put this set of characters in between. All right, so let's see what this looks like. So I'm going to come down here, exit out of the console again, clear it out, load the contents of the file again, and let's try that. So we'll say `l = LinkedList()`. All right, so `l.add(1)`, `l.add(2)`, `l.add(3)`. That seems enough, and then now if I type out `l` and hit enter, we get a nice string representation of the list. So you can see that we add every new node to the head, so we added one first. One ends up being the tail because it keeps getting pushed out, then two, and then finally three, so three is at the head. So far, we've only implemented a single method, which functions much like the `append` method on a Python list or an array, except it adds it to the start of the linked list; it pre-pends it. Like `append`, this happens in constant time. In the next video, let's add the ability to search through our list.

For the search operation, we're going to define a method that takes a value to search for and returns either the node containing the value if the value is found, or `None` if it isn't. So right after—actually, you know what—we'll make sure `wrapper` is the last function—our last method in our class—so we'll add it above it. So here we'll say `def search(self, key):`. In the last video, we implemented the `wrapper` method to provide a string representation of the list, so we're going to use similar logic here to implement the search function. We'll start by setting a local variable `current` to point to the head of the list. While the value assigned to `current` is a valid node—that is, it isn't `None`—we'll check if the data on that node matches the key that we're searching for. So `while current:` we'll say `if current.data == key:`, then we'll return `current`. If it does match, we'll go ahead and return it like we've done here, but if it doesn't, we'll assign the next node in the list to `current` and check again. So say `else: current = current.nextNode`. Once we hit the tail node and haven't found the key, `current` gets set to `None`, and the `while` loop exits. At this point, we know the list doesn't contain the key, so we can return `None`. Okay, that completes the body of our method. Let's add a docstring to document this. So up at the top, we'll say `"""Search for the first node containing data that matches the key. This is important because if our linked list contains more than one node with the same value, it doesn't matter; we're going to return the first one. With this implementation, we'll also say here that it returns the node or None if not found. In the worst-case scenario, we'll need to check every single node in the list before we find the key or fail, and as a result, this operation runs in linear time. So I'll say Takes O(n) or linear time."""`

So far, we haven't seen anything that indicates this data structure has any advantage over an array or a Python list, but we knew that. I mentioned the strength of linked lists comes in inserts and deletes at specific positions. We'll check that out in the next video, but as always, before we end this one, let's make sure everything works. So we'll load the contents of the file again. `l = LinkedList()`, and then we'll say `l.add(10)`, `l.add(20)`, 2 doesn't matter, `l.add(45)`, and one more—`l.add(15)`. Now we can say `l.search(45)`, and this returns a node or `None`, so we'll say `n = l.search(45)`, and then we'll hit enter. If this works, `n` should be a node. Okay, weirdly, `n` does not work here; at least it says it's not a node, which means I made a mistake in typing out our code. And looking at it immediately, it's fairly obvious. So this `return None` needs to be outside of the `while` loop. Okay, so I'm going to hit save now, so make sure it's on the same indentation here, which means it's outside the `while` loop, and then we'll run through this again. Okay, so `l = LinkedList()`, `l.add(10)`, `l.add(2)`, `l.add(45)`, and what was the last one we did? I believe it was 15, and now we should be able to say `l.search(45)`. Remember, we're assigning this to a node—to a variable—so `l.search(45)`, and there you go, we get that node back, and we can hit `l`, and we'll see a representation of our list. Okay, so again, in the next video, inserts and deletes at specific positions.

Insert operations on linked lists are quite interesting. Unlike arrays, where when you insert an element into the array, all elements after the particular index need to be shifted, with a linked list, we just need to change the references to `next` on a few nodes, and we're good to go. Since each node points to the next one, by swapping out these references, we can insert a node at any point in the list in constant time. Much like binary search, though, there's a catch. To find the node at that position we want to insert, we need to traverse the list and get to that point. We just implemented our search algorithm for the linked list type, and we know that this runs in linear time. So while actually inserting is fast, finding the position in the list you want to insert it is not. This is why I mentioned that there were some caveats to inserting. Anyway, let's see what this looks like in code. We'll define a method named `insert` that takes data to insert along with an index position. So we'll do this after `search`, right here. Say `def insert(self, data, index):`. You may be thinking, wait a minute, linked lists don't have index positions, right? And you're correct, but we can mimic that behavior by just counting the number of times we access `nextNode`. If the `index` value passed into this argument is 0, that means we want to insert the new node at the head of the list. This is effectively the same behavior as calling `add`, which means the logic is the same, so we don't need to repeat it. We can call the `add` method we wrote earlier. So we'll say `if index == 0:` or if `index is 0`, then `self.add(data)`. If the index is greater than 0, then we need to traverse the list to find the current node at that index. So `if index > 0:`. Now, before we do that, we need to create a new node containing the data we want to insert. So we'll say `new = Node(data)`. I'm going to assign `index`, the argument passed to our function, to a local variable named `position`, and the head of the list to a variable named `current`. `position = index`, `current = self.head`. Every time we call `current.nextNode`, meaning we're moving to the next node in the list, we'll decrease the value of `position` by 1. When `position` is zero, we'll have arrived at the node that's currently at the position we want to insert in. In reality, though, we don't want to decrease it all the way to zero. Imagine we have a list with five nodes, and we want to insert a node at position 3. To insert a node at position 3, we need to modify the nodes at positions 2 and 3. Node 2's `nextNode` attribute is going to point to the new node, and the new node's `nextNode` attribute will point to node 3. In this way, an insert is a constant time operation; we don't need to shift every single element; we just modify a few `nextNode` references. In a doubly linked list, we can use node 3 to carry out both of these operations. Node 3 in a doubly linked list would have a reference to node 2, and we can use this reference to modify all the unnecessary links. In a singly linked list, though, which is what we have, if we kept decreasing `position` until we're at 0, we arrive at node 3. We can then set the new node's `nextNode` property to point to node 3, but we have no way of getting a reference to node 2, which we also need. For this reason, it's easier to decrease `position` to just 1. When it equals 1, and stop at node 2. So in here we'll say `while position > 1:`. Now, while the position is greater than one, we'll keep calling `nextNode` and reassigning the current node. So `current = current.nextNode`, and at the same time, we'll decrement `position`. So `position -= 1`, which you can also succinctly write as `-= 1`. This way, when the position equals one, the loop exits, and `current` will refer to the node at the position before the insert point. So outside the `while` loop, we'll say `previous = current` and `next = current.nextNode`. To make things more clear, what I've done here is name the node before the new one `previous`, and the node after the new one `next`. All that's left to do now is to insert the new node between `previous` and `next`. So we'll say `previous.nextNode = new`, and then `new.nextNode = next`. Now it seems like there's an issue with variable naming here, and I'm most probably conflicting with some globally named `next` variable, so actually go ahead and call this `nextNode` and `previousNode`, so that we don't mess things up here. `previousNode`, so the `.nextNode` is obviously the attribute on a node, but this is just a local variable. Let's document this method. So up at the top, we'll add a docstring, and it will say `"""Inserts a new node containing data at index position. Insertion takes constant time, but finding the node at the insertion point takes linear time. Therefore, it takes an overall linear time."""` Let's add this to the next line. There we go. And then we'll say, this is why, even though we can easily insert a new node without having to shift the rest, ultimately adding to either the head or the tail, if you have a reference, is much more efficient.

We have one more operation to add to our linked list that will make it a robust data structure. Much like inserts, removing a node is actually quite fast and occurs in constant time, but to actually get to the node that we want to remove and modify the next connections, we need to traverse the entire list. In our worst case, so in the worst case, this takes linear time. Let's add this operation to our data structure. There are two ways we can define the `remove` method: one where we provide a key to remove as an argument, and one where we provide an index. Now, in the former, the key refers to the data the node stores, so in order to remove that node, we would first need to search for data that matches the key. I'm going to implement that first method, which we'll call `remove`, and I'll leave it up to you to get some practice in and implement a `removeAtindex` method to complete our data structure. So we'll add this after the `insert` method, right here. `remove` is going to accept a key, which we'll need to search for before we can remove a node. Earlier, we defined a `search` method that found a node containing data that matches a key, but we can't use that method as is for the implementation of `remove`. When we remove a node, much like the insert operation, we need to modify the `nextNode` references. The node before the match needs to point to the node after the match. If we use the `search` method we defined earlier, we get the node we want to remove as a return value, but because this is a singly linked list, we can't obtain a reference to the previous node. Like I said earlier, if this was a doubly linked list...

We could use the search method, since we would have a reference to that previous node. We'll start here by setting a local variable named `current` to point to the head. Let's also define a variable named `previous` that will set to `None` to keep track of the previous node as we traverse the list. Finally, let's declare a variable named `found` that we'll set to `False`. `found` is going to serve as a stopping condition for the loop that we'll define. We'll use the loop to keep traversing the linked list as long as `found` is `False`, meaning we haven't found the key that we're looking for. Once we've found it, we'll set `found` to `True`, and the loop terminates. So let's set up our loop. So we'll say `while current and not found`.

Here we're defining a `while` loop that contains two conditions. First, we tell the loop to keep iterating as long as `current` does not equal `None`. When `current` equals `None`, this means we've gone past the tail node, and the key doesn't exist. The second condition asks the loop to keep evaluating as long as `not found` equals `True`. Now this might be tricky because it involves a negation here. Right now, `found` is set to `False`, so `not found` (not `False`) equals `True`. This `not` operator flips the value. When we find the key and we set `found` to `True`, `not True` (`not found`) will equal `False` then, and the loop will stop. The `and` in the `while` loop means that both conditions—`current` being a valid node and `not found` equaling `True`—both have to be true. If either one of them evaluates to `False`, then the loop will terminate.

Now, inside the loop, there are three situations that we can run into. First, the key matches the current node's data, and `current` is still at the head of the list. This is a special case because the head doesn't have a previous node, and it's the only node being referenced by the list. Let's handle this case. So we'll say `if current.data == key and current is self.head` (which you can write out as `current == self.head` or `current is self.head`). Now, if we hit this case, we'll indicate that we found the key by setting `found` to `True`. And then this means that on the next pass, this is going to evaluate to `False` because `not True` will be `False`, and then the loop terminates. Once we do that, we want to remove the current node, and since it's the head node, all we need to do is point `head` to the second node in the list, which we can get by referencing the `next node` attribute on `current`. `self.head = current.nextNode`. So when we do this, there's nothing pointing to that first node, so it's automatically removed.

The next scenario is when the key matches data in the node, and it's a node that's not the head. So here we'll say `else if current.data == key`. If the current node contains the key we're looking for, we need to remove it. To remove the current node, we need to go to the previous node and modify its `next node` reference to point to the node after `current`. But first, we'll set `found` to `True`, and then we'll switch out the references. `previous.nextNode = current.nextNode`. So far, we haven't written any code to keep track of the previous node. We'll do that in our `else` case here. So if we hit the `else` case, it means that the current node we're evaluating doesn't contain the data that matches the key. So in this case, we'll make `previous` point to the current node and then set `current` to the next node. `previous = current` and `current = current.nextNode`. And that's it for the implementation of `remove`. Now we're not doing anything at the moment with the node we're removing, but it's common for `remove` operations to return the value being removed. So at the bottom, outside the `while` loop, let's return `current`.

And with that, we have a minimal implementation of a linked list and your first custom data structure. How cool is that? There's quite a bit we can do here to improve our data structure, particularly in making it easy to use, but this is a good place to stop before we move on to the next topic. Let's document our method. So the top, another docstring, and here we'll say "removes node containing data that matches the key. Also, it returns the node or `None` if the key doesn't exist. And finally, this takes linear time because in the worst-case scenario, we need to search the entire list." If you'd like to get in some additional practice implementing functionality for linked lists, two methods you can work on are `remove at index` and `node at index` to allow you to easily delete or read values in a list at a given index.

Now that we have a linked list, let's talk about where you can use them. The honest answer is not a lot of places. Linked lists are really useful structures to build for learning purposes because they're relatively simple and are a good place to start to introduce the kinds of operations we need to implement for various data structures. It is quite rare, however, that you will need to implement a linked list on your own. There are typically much better, and by that I mean much more efficient, data structures that you can use. In addition, many languages like Java, for example, provide an implementation of a linked list already.

Now that we have a custom data structure, let's do something with it. Let's combine the knowledge we have and look at how a sorting algorithm can be implemented across two different data structures. [Music] Now that we've seen two different data structures, let's circle back and apply what we know about algorithms to these new concepts. One of the first algorithms you learned about was binary search, and we learned that with binary search, there was one precondition: the data collection needs to be sorted. Over the next few videos, let's implement the merge sort algorithm, which is one of many sorting algorithms, on both arrays (or Python lists) and the singly linked list we just created. This way, we can learn a new sorting algorithm that has real-world use cases and see how a single algorithm can be implemented on different data structures.

Before we get into code, let's take a look at how merge sort works conceptually, and we'll use an array to work through this. We start with an unsorted array of integers, and our goal is to end up with an array sorted in ascending order. Merge sort works like binary sort by splitting up the problem into subproblems, but it takes the process one step further. On the first pass, we're going to split the array into two smaller arrays. Now, in binary search, one of these subarrays would be discarded, but that's not what happens here. On the second pass, we're going to split each of those subarrays into further smaller, evenly sized arrays, and we're going to keep doing this until we're down to single-element arrays. After that, the merge sort algorithm works backward, repeatedly merging the single-element arrays and sorting them at the same time. Since we start at the bottom by merging two single-element arrays, we only need to make a single comparison to sort the resulting merge array. By starting with smaller arrays that are sorted as they grow, merge sort has to execute fewer sort operations than if it sorted the entire array at once. Solving a problem like this by recursively breaking down the problem into subparts until it is easily solved is an algorithmic strategy known as divide and conquer. But instead of talking about all of this in the abstract, let's dive into the code. This way, we can analyze the runtime as we implement it.

For our first implementation of merge sort, we're going to use an array or a Python list. While the implementation won't be different conceptually for a linked list, we will have to write more code because of list traversal and how nodes are arranged. So once we have these concepts squared away, we'll come back to that. Let's add a new file here; we'll call this `merge_sort.py`. In our file, let's create a new function named `merge_sort` that takes a list. And remember, when I say list, unless I specify linked list, I mean a Python list, which is the equivalent of an array. So we'll say `def merge_sort(list):`. In the introduction to algorithms course, we started our study of each algorithm by defining the specific steps that comprise the algorithm. Let's write that out as a docstring in here, the steps of the algorithm, so that we can refer to it right in our code. This algorithm is going to sort the given list in ascending order. So we'll start by putting that in here as a simple definition: "sorts a list in ascending order." There are many variations of merge sort, and in the one we're going to implement, we'll create and return a new sorted list. Other implementations will sort the list we pass in, and this is less typical in an operation known as sort in place, but I think that returning a new list makes it easier to understand the code. Now, these choices do have implications, though, and we'll talk about them as we write this code. For our next bit of the docstring, let's write down the output of this algorithm. So "returns a new sorted list." Merge sort has three main steps. The first is the divide step, where we find the midpoint of the list. So I'll say "divide: find the midpoint of the list and divide into sub-lists." The second step is the conquer step, where we sort the sub-list that we created in the divide step. So we'll say "recursively sort the sub-lists created in previous step." And finally, the combine: "merge the sorted sub-lists created in previous step."

When we learned about algorithms, we learned that a recursive function has a basic pattern. First, we start with a base case that includes a stopping condition. After that, we have some logic that breaks down the problem and recursively calls itself. Our stopping condition is our end goal: a sorted array. Now, to come up with a stopping condition or a base case, we need to come up with the simplest condition that satisfies this end result. So there are two possible values that fit: a single-element list or an empty list. Now, in both of these situations, we don't have any work to do. If we give the `merge_sort` function an empty list or a list with one element, it's technically already sorted. We call this naively sorting. So let's add that as our stopping condition. We'll say `if len(list) <= 1:` then we can return the list. Okay, so this is a stopping condition, and now that we have a stopping condition, we can proceed with the list of steps. First, we need to divide the list into sublists. To make our functions easier to understand, we're going to put our logic in a couple different functions instead of one large one. So I'll say `left_half, right_half = split(list)`. So here we're calling a `split` function that splits the list we pass in and returns two lists split at the midpoint. Because we're returning two lists, we can capture them in two variables. Now you should know that this `split` function is not something that comes built into Python. This is a global function that we're about to write. Next is the conquer step, where we sort each sub-list and return a new sorted sub-list. So we'll say `left = merge_sort(left_half)` and `right = merge_sort(right_half)`. This is the recursive portion of our function. So here we're calling `merge_sort` on this divided sublist. So we divide the list into two here, and then we call `merge_sort` on it again. This further splits that sublist into two in the next pass through of `merge_sort`. This is going to be called again and again and again until we reach our stopping condition where we have single-element lists or empty lists. When we've subdivided until we cannot divide any more, then we'll end up with a `left` and a `right` half, and we can start merging backward. So we'll say `return merge(left, right)`. That brings us to the combined step. Once two sub-lists are sorted and combined, we can return it. Now, obviously, none of these functions—`merge`, `merge_sort`—well, `merge_sort` is written, but `merge` and `split` haven't been written. So all we're going to do here if we run it is raise an error. So in the next video, let's implement the `split` operation.

The first bit of logic we're going to write is the divide step of the algorithm. This step is fairly straightforward and only requires a few lines of code but is essential to get the sorting process going. All right, so as we saw earlier, we're going to call the function for the divide step, `split`. So we'll say `def split(list):`. `split` is going to take as an argument a list to split up. Let's document how this function works. So we'll say "divide the unsorted list at midpoint into sub-lists," and it's always good to say what we're returning as well. So we'll say "returns two sub-lists, `left` and `right`." All right, so the first step is to determine the midpoint of this list, of this array. We're going to use the floor division operator for this. Floor division carries out a division operation, and if we get a non-integer value like 2.5 back, it just gets rounded down to two. We'll define the midpoint to be the length of the list divided by two and then rounded down. So `len(list) // 2`. Okay. Once we have the midpoint, we can use the slicing notation in Python to extract portions of the list we want to return. For instance, we can define `left` as the left sub-list that goes all the way from the start of the list all the way up to the midpoint without including the midpoint. Now, over here, we're using the slicing syntax where it's like using the, you know, subscript notation to access a value from a list, but instead, we give two index values as a start and stop. If we don't include a start value, as I've done here, Python interprets that as starting from the zeroth index or the start of the list. Now, similarly, we can define `right` to be values on the right of the midpoint, so starting at the midpoint and going all the way up to the end of the list. So a couple of things to note: as I said earlier, when you don't include the starting index, it interprets it as to start at the very beginning of the list. The index you give as the stopping condition, that value is not included in the slice. So over here, we're starting at the very beginning of `list`, and we go all the way up to `midpoint`, but not including `midpoint`. And then `right` starts at `midpoint`, so it includes that value and then goes all the way to the end of the list. Now, once we have these two sub-lists, we can return them. So we'll `return left, right`. Notice that we're returning two values here, and then in the `merge_sort` function, when we call that `split` function, we're declaring two variables, `left_half` and `right_half`, to assign so that we can assign these two sublists to them. Okay, and that's all there is to the `split` function. In the next video, let's implement the crucial portion of the merge sort logic.

Once we run the `split` function recursively over the array, we should end up with several single-member or empty arrays. At this point, we need to merge them all back and sort them in the process, which is what our `merge` function is for. The `merge` function is going to take two arrays or lists as arguments, and to match the naming conventions we used in the `split` function, we'll call this `left` and `right` as well. So we'll say `def merge(left, right):`. Now, like before, let's add some documentation to our function. So this function merges two lists or arrays, sorting them in the process, and then it returns a new merged list. Since our function is going to return a new list, let's start by creating one. Now, in the process of merging, we need to sort the values in both lists. To sort, we need to compare values from each array or each list. So next, let's create two local variables to keep track of index values that we're using for each list. So the convention here is `i` and `j`, so we'll stick to it. So `i = 0`, `j = 0`. As we inspect each value in either list, we'll use the variables to keep track of the indexes of those values. So we'll use `i` to keep track of indexes in the `left` list and `j` for indexes in the `right` list. When merging, we want to keep sorting the values until we've worked through both lists. So for our loop, let's set up two conditions with an `and` operator. So we'll say `while i < len(left) and j < len(right):`. So here we're ensuring that as long as `i` is less than the length of the `left` list, and the `and` is important, and `j` is less than the length of the `right` list, we're going to keep executing the code. Now, `i` and `j` are both set to zero initially, which means that our first comparison operation will be on the first element of each list respectively. So we'll say `if left[i] < right[j]`. So `i` is zero, so this is going to get the first value out of the `left` list, is less than `right[j]`, and again here `j` is zero, so we're going to get the first value out of the `right` list. Now, if the value at index `i` in the `left` list is less than the value at index `j` in the `right` list, what do we do? Well, that means the value being compared in `left` is less than the value in the `right` and can be placed at position 0 in the new array `l` that we created earlier. So here we'll say `l.append(left[i])`. Since we've read and done something with the value at position `i`, let's increment that value, so we move forward to evaluate the next item in the `left` list. `i += 1`. Okay. Next is an `else` statement, and here we'll say, if the value at index `i`, so `i` don't have to write out the actual logic because it's implied. So here we're saying that `left` the value at `left` is less than the value at `right`. Now, in the `else` clause, if the value at, so `i` equals, is greater, and I haven't written out that condition because it's implied. So here we're saying if the value in the `left` is less than the value in the `right`. So in the `else` clause, it's going to mean that the value in the `left` is either greater than or equal to the value in the `right`. But when we hit the `else` clause, if the value at index `i` in the `left` list is greater, then we place the value at index `j` from the `right` list at the start of the new one list `l`, and similarly increment `j`. So here we'll say `l.append(right[j])` and then `j += 1`. Doing this doesn't necessarily mean that in one step we'll have a completely sorted array, but remember that because we start with single-element arrays and combine with each merge step, we will eventually sort all the values more than one time, and by the time the entire process is done, all the values are correctly sorted. Now, this isn't all we need to do in the merge step, however. There are two situations we can run into: one where the `left` array is larger than the `right`, and vice versa. So this can occur when an array containing an odd number of elements needs to be split. So how do you split a three-element array or list? Well, the `left` can have two elements, and the `right` can have one, or the other way around. In either case, our `while` loop uses an `and` condition where the variables used to store the indexes need to be less than the length of the lists. If the `left` list is shorter than the `right`, then the first condition returns `False`, and the entire loop returns `False` because it's an `and` condition. This means that in such an event, when the `while` loop terminates, not all the values in the `right` list will have been moved over to the new combined list. So to account for this, let's add two more `while` loops. The first `while` loop is going to account for a situation where the `right` list is shorter than the `left`, and the previous loop terminated because we reached the end of the `right` list first. So in this case, what we're going to do is simply add the remaining elements in the `left` to the new list. We're not going to compare elements because we're going to assume that within a list, the elements are already sorted.

So, while i is less than the length of left, then it's the same logic: l.append(left[i]) and i += 1. So the while loop is going to have the similar condition, keep the loop going until it's at the last index. Inside the body, we're incrementing the index with every iteration of the loop. Our final loop accounts for the opposite scenario where the left was shorter than the right. The only difference here is that we're going to use the variable j along with the right list. So we'll say: while j is less than the length of right, l.append(right[j]) and j += 1.

Okay, let's stop here. In the next video, let's test out merge sort, make sure our code is running correctly and everything is written well, and then we'll wrap up this stage by documenting our code and evaluating the run time of our algorithm.

In the last video, we completed our implementation for the merge sort algorithm, but we didn't test it in any way. Let's define a new list at the bottom that contains several numbers. You can put whatever you want in there, but make sure that the numbers are not in order. I'll call mine a_list, and in here we'll say 54, 26, or 62, doesn't matter, 93, 17, 77, 31. Just add enough so that you can make out that it's sorted. Okay.

Next, we're going to call the merge sort algorithm and pass in our list. Let's assign this to some variables, so we'll say l = merge_sort(a_list). And then, if it works correctly, we should be able to print this list and see what it looks like. So I'm going to hit save down here in the console. We'll tap out python merge_sort.pi. And before I hit enter, I actually noticed I made an error in the last video, but I'll hit enter anyway, and you should see the error pop up.

Okay, so what I forgot to do, which is a pretty crucial part of our algorithm, is in the merge function, I forgot to return the list containing the sorted numbers after carrying out all this logic. So here at the bottom, we'll say return l. All right, we'll save again, and now we'll clear this out and try that one more time. And there we go. You should see a sorted list printed out. We can write out a more robust function to test this because with bigger arrays, visually evaluating that printed list won't always be feasible. So bring this back down, let's get rid of this, and we'll call our function verify_sorted. This will take a list.

First, we're going to check inside the body of the function; we'll check the length of the list. If the list is a single element list or an empty list, we don't need to do any unnecessary work because remember, it is naively sorted. So we'll say: if n == 0 or if n == 1, then we'll return True. We've verified that it's sorted. Now, to conclude our function, we're going to write out one line of code that will actually do quite a bit of work. So first we'll say: return list[0] < list[1]. So we'll take the first element out of the list and we'll compare and see if that's less than the second element in the list. Okay. So first, we'll check that the first element in the list is less than the second element in the list. This returns either True or False, so we can return that directly. But this isn't sufficient. If it were, we could trick the verify function by only sorting the first two elements in the list. So to this return statement, we're going to use an and operator to add on one more condition. For this condition, we're going to make a recursive function call back to verify_sorted, and for the argument, we're going to pass in the list going from the second element all the way to the end.

Let's visualize how this would work. We'll use a five-element list as an example. So we'll call verify_sorted and pass in the entire list. This list is not one or zero elements long, so we skip that first if statement. There's only one line of code left in the function, and first we check that the element at index 0 is less than the element at index 1. If this is False, the function returns immediately with a False value. An and operator requires both conditions to be True for the entire line of code to return True. Since the first condition evaluates to False, we don't need to bother evaluating the second. The second condition is a recursive call with a sub-list containing elements from the original list starting at position 1 and going to the end. So on the second call, again we can skip that first if statement and proceed to check whether the value at element 0 is less than the value at element 1. Remember that because this list is a sub-list of the original starting at the element that was the second element in the original list, by comparing the elements at position 0 and 1 in the sub-list, we're effectively comparing the elements at position 1 and 2 in the original list. With each recursive call, as we create new sub-lists that start at index position 1, we're able to check the entire list without having to specify any checks other than the first two elements. Since this is a recursive function, it means we need a stopping condition, and we have it already; it's that first if condition. As we keep making sub-lists, once we reach a single element list, that element is already sorted by definition, so we can return True. Since this recursive function call is part of an and condition, it means that every single recursive call has to return True all the way back to the beginning for our top-level function to return True and for the function to say, "Yes, this is sorted."

Now we could have easily done this using an iterative solution and a for loop, but this way you get another example of recursion to work through and understand. So let's use this function at the bottom. We'll say: print(verify_sorted()). First we'll pass in a_list. Oops, we got rid of that, didn't we? Okay, let me write it out again. So a_list = and I think I have those original numbers here somewhere. So we'll say 54, 26, 93. Okay, and then we assigned to l the result of calling merge_sort on a_list. Okay, so now here we're going to use the verify_sorted function, and we'll check first that a_list is sorted; that should return False. And then we'll check the same call on; we'll pass in l, and this should return True. Okay, so now at the bottom here in the console, we'll call python merge_sort.pi, and there we go. It returned False for a_list, meaning it's not sorted, but l is sorted. Cool. So our merge sort function works.

In the next video, let's talk about the cost of this algorithm. If we go back to the top level, the merge_sort function, what is the run time of this function look like? And what about space complexity? How does memory usage grow as the algorithm runs? To answer those questions, let's look at the individual steps, starting with the split function. In the split function, all we're doing is finding the midpoint of the list and splitting the list at the midpoint. This seems like a constant time operation, but remember that the split function isn't called once; it's called as many times as we need it to to go from the initial list down to a single element list. Now this is a pattern we've seen a couple times now, and we know that overall this runs in logarithmic time. So let's add that as a comment. So here I'll say: # takes overall O(log n) time. Now there's a caveat here, but we'll come back to that.

So next up is the merge step. In the merge step, we've broken the original list down into single element lists, and now we need to make comparison operations and merge them back in the reverse order. For a list of size n, we will always need to make an n number of merge operations to get back from single element lists to a merged list. This makes our overall runtime O(n * log n) because that's an n number of merge steps multiplied by log n number of splits of the original list. So to our merge step here, let's add a comment. We'll say: # it runs in overall linear time. Right, it takes an n number of steps, number of merge steps. But now that we have these two—so linear here and logarithmic here—we can multiply these and say that the merge sort function, the top-level function, we can conclude that the runtime of the overall sorting process is O(n * log n).

Now what about that caveat I mentioned earlier? So if we go back to our split function here, right here, there we go. Let's take a look at the way we're actually splitting the list. So we're using Python's list slicing operation here and passing in two indexes where the split occurs. Now if you go and poke around the Python documentation, which I've done, it says that a slicing operation is not a constant time operation and in fact has a runtime of O(k), where k represents the slice size. This means that in reality, our implementation of split, this implementation of split, does not run in logarithmic time, but k * logarithmic time because there is a slice operation for each split. This means that our implementation is much more expensive. So overall, that makes our overall top-level merge sort function not n * log n, but k * n * log n, which is much more expensive. Now let's get rid of all that. To fix this, we would need to remove this slicing operation. Now we can do that by using a technique we learned in a previous course, in the introduction to algorithms course. We looked at two versions of binary search in Python, a recursive and an iterative version. In the recursive one, we use list slicing with every recursion call, but we achieve the same end result using an iterative approach without using list slicing. Over there, we declared two variables to keep track of the starting and ending positions in the list. We could rewrite merge sort to do the same, but I'll leave that as an exercise for you. If you want some hints, if you want any direction, I've included a link in the notes with an implementation.

So that is time complexity. Now, just so we know before moving on, for Python here, our overall run time is not what I've listed here, but this is what the actual run time of the merge sort algorithm looks like. So the merge step runs in linear time, and the split step takes logarithmic time for an overall n * log n, and that is how merge sort actually works. Okay, so what about space complexity? The merge sort algorithm takes linear space, and this is weird to think about it first, but as always, a visualization helps. So if we start at the top again with our full list and carry out the split method until we have single-element lists, each of these new lists takes up a certain amount of space. So the second level here, we have two lists where each takes up an n/2 amount of space. Now this makes it seem that the sum of all this space is the additional space needed for merge sort, but that's not actually the case. In reality, there are two factors that make a difference. First, not every single one of these sub-lists are created simultaneously. At step two, we create two n/2 size sub-lists. When we move to the next step, however, we don't hold on to the n/2 sub-lists and then create four n/4 size sub-lists for the next split. Instead, after the four n/4 size sub-lists are created, the n/2 ones are deleted from memory. There's no reason to hold on to them any longer. Now the second point is that our code doesn't execute every path simultaneously. Think of it this way: when we pass our list to the top-level merge sort function, our implementation calls split, which returns a left half and a right half. The next line of code then calls merge_sort on the left half again. This runs the function, the merge_sort function again with a new list. In that second run of the function, split is called again. We get a second left and right half, and then again, like before, we call merge_sort on this left half as well. What this means is that the code walks down the left path all the way down until that initial left half is sorted and merged back into one array. Then it's going to walk all the way down the right path and sort that until we're back to that first split with two n/2 sized sub-lists. Essentially, we don't run all these paths of code at once, so the algorithm doesn't need additional space for every sub-list. In fact, it is the very last step that matters. In the last step, the two sub-lists are merged back into the new sorted list and returned. That sorted list has an equal number of items as the original unsorted list, and since this is a new list, it means that at most the additional space the algorithm will require at a given time is n. Yes, at different points in the algorithm, we require log n amount of space, but log n is smaller than n, and so we consider the space complexity of merge sort to be linear because that is the overall factor.

Okay, that was a lot. So let's stop here. Don't worry if you've got questions about merge sort because we're not done yet. Over the next few videos, let's wrap up this course by implementing merge sort on a linked list. [Music]

Over the last few videos, we implemented the merge sort algorithm on the array or list type in Python. Merge sort is probably the most complicated algorithm we've written so far, but in doing so, we learned about an important concept: divide and conquer. We also concluded the last video by figuring out the run time of merge sort based on our implementation. Over the next few videos, we're going to implement merge sort again, this time on the linked list type. In doing so, we're going to get a chance to see how the implementation differs based on the data structure while still keeping the fundamentals of the algorithm the same, and we'll also see how the run time may be affected by the kinds of operations we need to implement.

Let's create a new file to put our second implementation of merge sort in. So file over here, new file, and it's going to have a rather long name. We'll call this linked_list_merge_sort.pi. We're going to need the linked list class that we created earlier, so we'll start at the top by importing the linked list class from the linkedlist.pi file. The way we do that is we'll say: from linked_list import linked_list. Right, so that imports the class. Uh, let's test if this works really quick. We'll just do something like: l = linked_list(), l.add(10), or one doesn't matter, print(l). Okay, and if I hit save and then down here we'll say python linked_list_merge_sort.pi. Okay, it works. So this is how we get some of the code, how we reuse the code that we've written in other files into this current file. And get rid of this now. Okay, like we did with the first implementation of merge sort, we're going to split the code up across three functions: the main function, merge_sort, a split function, and a merge function. Now, if you were to look up a merge sort implementation in Python, both for a regular list, an array, or a linked list, you would find much more concise versions out there, but they're kind of hard to explain. So splitting it up into three will sort of help it, you know, be easier to understand. So we'll call this merge_sort at the top level, and this time it's going to take a linked list. Let's add a docstring to document the function. So say that this function sorts a linked list in ascending order. And like before, we'll add the steps in here. So we'll say: """You first recursively divide the linked list into sub-lists containing a single node, then we repeatedly merge these sub-lists to produce sorted sub-lists until one remains, and then finally this function returns a sorted linked list.""" The implementation of this top-level merge function is nearly identical to the array or list version we wrote earlier. So first, we'll provide a stopping condition or two. If the size of the list is one or it's an empty list, we'll return the linked list since it's naively sorted. So if linked_list.size, remember that function we run, == 1, then we'll return linked_list. Else if linked_list.head is None, meaning it's an empty list, then we'll return linked_list as well.

Okay. Next, let's split the linked list into a left and right half. Conceptually, this is no different, but in practice, we need to actually traverse the list. We'll implement a helper method to make this easier, but we'll say: left_half, right_half = split(linked_list). Now once we have two sub-lists, like before, we can call merge_sort, the top-level function, on each. So: left = merge_sort(left_half) and right = merge_sort(right_half). Finally, we'll merge these two top-level sub-lists and return it. So: merge(left, right). Okay, nothing new here, but in the next video, let's implement the split logic.

The next step in the merge sort algorithm is the divide step, or rather an implementation of the split function. So down here, we'll call this split. Like before, and this is going to take a linked list. Documenting things is good, and we've been doing it so far, so let's add a docstring: """Divide the unsorted list at midpoint into sub-lists.""" Now, of course, when I say sub-lists here, I mean sub-linked lists, but that's a long word to say. Now here's where things start to deviate from the previous version with the list type. We could rely on the fact that finding the midpoint using an index and list slicing to split into two lists would work even if an empty list was passed in. Since we have no automatic behavior like that, we need to account for this when using a linked list. So our first condition is: if the linked list is None or if it's empty, that is, if head is equal to None. So we'll say: if linked_list == None or you can write is there, it doesn't matter, or linked_list.head is None, well linked_list can be None, for example, if we call split on a linked list containing a single node, a split on such a list would mean left would contain the single node while right would be None. Now, in either case, we're going to assign the entire list to the left half and assign None to the right. So we'll say: left_half = linked_list and then right_half = None. You could also assign the single-element list or None to left and then create a new empty linked list assigned to the right half, but that's unnecessary work. So now that we've done this, we can return left_half and right_half. So that's our first condition. Let's add an else clause to account for non-empty linked lists. First, we'll calculate the size of the list. Now this is easy because we've done the work already, and we can just call the size method that we've defined. We'll say: size = linked_list.size. Using this size, we can determine the midpoint. So: mid = size // 2. Once we have the midpoint, we need to get the node at that midpoint. Now make sure you hit command s to save here, and we're going to navigate back to linkedlist.pi. In here, we're going to add a convenience method at the very bottom, right before the wrapper function, right here. And this convenience method is going to return a node at a given index. So I'll call this node_at_index, and it's going to take an index value. This way, instead of having to traverse the list inside of our split function, we can simply call node_at_index and pass it the midpoint index we calculated to give us the node right there, so we can perform the split. Okay, so this method accepts as an argument the index we want to get the node for. If this index is zero, then we'll return the head of the list. So: if index == 0: return self.head. The rest of the implementation involves traversing the linked list and counting up to the index as we visit each node. The rest of the implementation involves traversing the linked list and counting up to the index as we visit each node. So I'll add an else clause here, and we'll start at the head. So we'll say: current = self.head. Let's also declare a variable called position to indicate where we are in the

List: We can use a while loop to walk down the list. Our condition here is as long as the position is less than the index value. So I'll say, while position is less than index. Inside the loop, we'll assign the next node to current and increment the value of position by one. So, current = current.nextNode; position += 1. Once the position value equals the index value, current refers to the node we're looking for, and we can return it. We'll say return current. Let's get rid of all this empty space. There we go. Now, back in linkedListMergeSort.pi, we can use this method to get at the node after we've calculated the midpoint to get the node at the midpoint of the list. So we'll say midNode = linkedList.nodeAtIndex. And here I'm going to do something slightly confusing; I'm going to do mid - 1. Remember, we're subtracting 1 here because we used size to calculate the midpoint, and like the len function, size will always return a value greater than the maximum index value. So think of a linked list with two nodes; size would return two. The midpoint, though, and the way we're calculating the index, we always start at zero, which means size is going to be one greater than that. So we're going to deduct one from it to get the value we want, but we're using the floor division operator, so it's going to round that down even more. No big deal. With the node at the midpoint now that we have this midNode, we can actually split the list. So first, we're going to assign the entire linked list to a variable named leftHalf. So, leftHalf = linkedList. This seems counterintuitive, but make sense in a second. For the right half, we're going to assign a new instance of linkedList. So, rightHalf = linkedList. This newly created list is empty, but we can fix that by assigning the node that comes after the midpoint. So, after the midpoint of the original linked list, we can assign the node that comes after that midpoint node as the head of this newly created right linked list. So here we'll say rightHalf.head = midNode.nextNode. Once we do that, we can assign None to the nextNode property on midNode to effectively sever that connection and make what was the midNode now the tail node of the left linked list. So I'll say midNode.nextNode = None. If that's confusing, here's a quick visualization of what just happened. We start off with a single linked list and find the midpoint. The node that comes after the node at midpoint is assigned to the head of a newly created linked list, and the connection between the midpoint node and the one after is removed. We now have two distinct linked lists split at the midpoint, and with that we can return the two sublists. So we'll return leftHalf and rightHalf. In the next video, let's tackle our merge function.

In the last video, we defined an implementation for the version of the split function that works on linked lists. It contained a tiny bit more code than the array or list version that was expected. The merge function is no different because, like with the split function, after we carry out a comparison operation, we also need to swap references to corresponding nodes. All right, let's add our merge function over here at the bottom, below the split functions. We'll call this merge, and it's going to take a left and right. Now, because this can get complicated, we're going to document this function extensively, and as always, we're going to start with a docstring. So we'll say that this function merges two linked lists, sorting by data in the nodes, and it returns a new merged list. Remember that in the merge step, we're going to compare values across two linked lists and then return a new linked list with nodes where the data is sorted. So first, we need to create that new linked list. Let's add a comment in here. We'll say, create a new linked list that contains nodes from; let's add a new line, merging left and right. Okay, and then create the list: merged = new linkedList. To this list, we're going to do something unusual; we're going to add a fake head. This is so that when adding sorted nodes, we can reduce the amount of code we have to write by not worrying about whether we're at the head of the list. Once we're done, we can assign the first sorted node as the head and discard the fake head. Now, this might not make sense at first, but not having to worry about whether the new linked list already contains a head or not makes the code simpler. We'll add another comment and a fake head that is discarded later. We'll say merged.add(0). Like we've been doing so far, we'll declare a variable named current to point to the head of the list. Set current to the head of the linked list, and then current = merged.head. Next, we'll get a reference to the head on each of the linked lists, left and right. So we'll say, obtain head nodes for left and right linked lists, and here's call this leftHead = left.head and rightHead = right.head. Okay, so with that setup out of the way, let's start iterating over both lists. So another comment, iterate over left and right as long or we'll say, until we reach the tail node of either. And we'll do that by saying while leftHead or rightHead. So this is a pattern that we've been following all along; we're going to iterate until we hit the tail nodes of both lists, and we'll move this pointer forward every time so that we traverse the list with every iteration. If you remember the logic behind this from the earlier version, once we hit the tail node of one list, if there are nodes left over in the other linked list, we don't need to carry out a comparison operation anymore, and we can simply add those nodes to the merged list. The first scenario we'll consider is if the head of the left linked list is None. This means we're already past the tail of left, and we can add all the nodes from the right linked list to the final merge list. So here I'll say, if the head node of left is None, we're past the tail, add the node from the right from right to merged linked list. So here we'll say if leftHead is None, current.nextNode – remember current points to the head of the merge list that we're going to return – so here we're setting its next node reference to the head node on the right linked list. So we'll say rightHead. Then when we do that, we'll move the right head forward to the next node. So let's say rightHead = rightHead.nextNode. This terminates the loop on the next iteration. Let's look at a visualization to understand why. Let's say we start off with a linked list containing four nodes. So we keep calling split on it until we have lists with just a single head, single node linked lists essentially. So let's focus on these two down here that we'll call left and right. We haven't implemented the logic for this part yet, but here we would compare the data values and see which one is less than the other. So we'll assume that left's head is lesser than right's head. So we'll set this as the next node in the final merge list. Left is now an empty length list, so left.head = None. On the next pass through the loop, leftHead is None, which is the situation we just implemented here. We can go ahead and now assign rightHead as the next node in the merge linked list. We know that right is also a singly linked list. Here's the crucial bit: When we move the pointer forward by calling nextNode on the right node, there is no node, and the right linked list is also empty now, which means that both leftHead and rightHead are None, and either one of these would cause our loop condition to terminate. So what we've done here is encoded a stopping condition for the loop. So we need to document this because it can get fuzzy. So right above that line of code, I'll say, call next on right to set loop condition to false. Okay, there's another way we can arrive at this stopping condition, and that's in the opposite direction: if we start with the rightHead being None. So here I'll say, I'm going to add another comment, if – oops, not there, there – if the head node of right is None, we're past the tail, then we'll say add the tail node from left to merged linked list, and then we'll add that condition. We'll say else if rightHead is None. Now remember, we can enter these even if leftHead is None; we can still go into this condition; we can still enter this if statement and execute this logic because the while loop, the loop condition here is an or statement. So even if leftHead is false, if this returns true because there's a value there, there's a node there, the loop will keep going. Okay, now in this case, we want to set the head of the left linked list as the next node on the merge list. So this is simply the opposite of what we did over here. We'll set current.nextNode = leftHead, and then we'll move – so after doing that, we can move the variable pointing to leftHead forwards, which as we saw earlier is past the tail node and then results in the loop terminating. So we'll say leftHead = leftHead.nextNode, and we'll add that comment here as well. So we'll say, call next on left to set loop condition to false because here rightHead is None, and now we make leftHead None. These two conditions we looked at, where either the leftHead or rightHead were at the tail nodes of our respective lists, those are conditions that we run into when we've reached the bottom of our split where we have single-element linked lists or empty linked lists. Let's account for our final condition where we're evaluating a node that is neither the head nor the tail of the list, and this condition we need to reach into the nodes and actually compare the data values to one another before we can decide which node to add first to the merged list. So here, this is an else because we've arrived at our third condition, third and final, and here we'll say, not at either tail node, obtain node data to perform comparison operations. So let's get each of those data values out of the respective nodes so that we can compare it. So we'll say leftData = leftHead.data and rightData = rightHead.data. Okay, what do we do next? Well, we compare, but first let's add a comment. So we'll say, if data on left is less than right, set current to left node and then move – actually, we'll add this in a second. So here we'll say if leftData < rightData, then current.nextNode = leftHead, and then we'll add a comment and we'll say, move leftHead to next node on that list. So we'll say leftHead = leftHead.nextNode. Just as our comment says, we'll check if the leftData is less than the rightData. If it is, since we want a list in ascending order, we'll assign the left node to be the next node in the merged list. We'll also move the leftHead forward to traverse down to the next node in that particular list. Now, if left is larger than right, then we want to do the opposite. So we'll go back to spaces, another comment, if data on left is greater than right, set current to right node. Okay, so else, here we assign the rightHead to be the next node in the merge list. So current.nextNode = rightHead, and then comment, move rightHead to next node, so rightHead = rightHead.nextNode. Okay, after doing that, we move the rightHead pointer to reference the next node in the right list, and finally, at the end of each iteration of the while loop – so not here, but two spaces back, right – make sure we're indented at the same level as the while – so we got to go, yep – or not the same level as the while, but the same outer scope, and then there we're going to say, move current to next node, so current = current.nextNode. Okay, don't worry if this is confusing; as always, we'll look at a visualization in just a bit. So we'll wrap up this function by discarding that fake head we set earlier, setting the correct node as head, and returning the linked list. So we'll add a comment, discard fake head and set first merged node as head. So here we'll say head = merged.head.nextNode, and then merged.head = head, and finally, return merged. Okay, we wrote a lot of code here; a lot of it was comments, but still, it's a bunch. Let's take a quick break. In the next video, we'll test this out, evaluate our results, and determine the runtime of our algorithm.

Okay, first things first, let's test out our code. Now, we'll keep it simple because writing a robust verify function would actually take up this entire video. Instead, I'll leave that up to you to try as homework. Okay, so at the very end, let's create a new linked list. Let's add a few nodes to this. So l.add – I'm going to copy-paste this so it makes it easier for me not to have to retype a bunch – so I'll add 10, uh, then set 2, 44, 15, and something like 200. Okay, then we'll go ahead and print l so that we can inspect this list. Next, let's create a, declare variable here. So we'll call this sortedLinkedList, and to this we're going to assign the result of calling mergeSort on l, and then we'll print this: sortedLinkedList. Since we've taken care of all the logic, we know that this gets added in as nodes, and then let's see what this looks like. All right, so hit save and then bring up the console. We're going to type out python linkedList_mergeSort.pi and then enter. Okay, so we see that linked list we first created. Remember that what we add first, right, that eventually becomes a tail or right, yeah. So 10 is the tail; 200 is the last one. So 200 is the head because I'm calling add; it simply adds each one to the head of the list. So here we have 10, 2, 44, 15, and 200 in the order we added, and then the sorted linked list sorts it out, so it's 2, 10, 15, 44, and 200. Look at that, a sorted linked list.

Okay, so let's visualize this from the top. We have a linked list containing five nodes with integers 10, 2, 44, 15, and 200 as data respectively. Our mergeSort function calls split on this list. The split function calls size on the list and gets back 5, which makes our midpoint 2. Using this midpoint, we can split the list using the nodeAtIndex method. Remember that when doing this, we deduct 1 from the value of mid, so we're going to split here using an index value of 1. Effectively, this is the same since we're starting with an index value of 0; 1 means we split after node 2. We assign the entire list to leftHalf, then create a new list and assign that to rightHalf. We can assign node 3 at index value 2 as the head of the right list and remove the references between node two and node three. So far so good, right? Okay, so now we're back in the mergeSort function after having called split, and we have two linked lists. Let's focus on just the left half because if you go back and look at our code, we're going to call mergeSort on the left linked list again. This means the next thing we'll do is run through that split process. Since this is a linked list containing two nodes, this means that split is going to return a new left and right list, each with one node. Again, we're back in the mergeSort function, which means that we call mergeSort on this left list again. Since this is a single-node linked list, on calling mergeSort on it, we immediately return before we split since we hit that stopping condition. So we go to the next line of code, which is calling mergeSort on the right list as well, but again we'll get back immediately because we hit that stopping condition. Now that we have a left and right that we get back from calling mergeSort, we can call merge on them. Inside the merge function, we start by creating a new linked list and attaching a fake head. Then we evaluate whether either the left or the right head is None. Since neither condition is true, we go to the final step where we evaluate the data in each node. In this case, the data in the right node is less than the left node, so we assign the right node as the next node in the merge linked list and move the rightHead pointer forward. In the merge linked list, we move our current pointer forward to this new node we've added, and that completes one iteration of the loop. On the next iteration, rightHead now points to None since that was a single-node list, and we can assign the rest of the left linked list, which is effectively the single node, over to the merge linked list. Here we discard the fake head, move the next node up to be the correct head, and return the newly merged sorted linked list. Remember that at this point, because rightHead and leftHead pointed to None, our while loop terminated. So in this way, we recursively split and repeatedly merge sub-lists until we're back with one sorted linked list. The merge sort algorithm is a powerful sorting algorithm, but ultimately it doesn't really do anything complicated; it just breaks the problem down until it's really simple to solve. Remember the technique here, which we've talked about before, is called divide and conquer. So I like to think of merge sort in this way: There's a teacher at the front of the room, and she has a bunch of books that she needs to sort into alphabetical order. Instead of doing all that work herself, she splits that pile into two and hands it to two students at the front. Each of those students splits it into two more and hands it to the four students seated behind them. As each student does this, eventually a bunch of single students has two books to compare, and they can sort it very easily and hand it back to the student who gave it to them in front of them, who repeats the process backwards. So ultimately, it's really simple work; it's just efficiently delegated. Now, back to our implementation here, let's talk about runtime. So far, other than the node swapping we had to do, it seems like most of our implementation is the same, right? In fact, it is, including the problems that we ran into in the list version as well. So in the first implementation of mergeSort, we thought we had an algorithm that ran in Big O of n log n, but turns out we didn't. Why? Well, the Python list slicing operation, if you remember, actually takes up some amount of time, amounting to Big O of k. A true implementation of merge sort runs in quasi-linear or log-linear time, that is n times log n. So we almost got there, but we didn't. Now, in our implementation of mergeSort on a linked list, we introduce the same problem. So if we go back up to the merge, or rather the split function, this is where it happens. Now, swapping node references, that's a constant-time operation; no big deal. Comparing values also constant time. The bottleneck here, like list slicing, is in splitting a linked list at the midpoint. If we go back to our implementation, you can see here that we use the nodeAtIndex method, which finds the node we want by traversing the list. This means that every split operation incurs a Big O of k cost, where k here is the midpoint of the list, effectively n by 2, because we have to walk down the list counting up the index until we get to that node. Given that overall splits take logarithmic time, our split function, just like the one we wrote earlier, incurs a cost of Big O of k log n. So here we'll say it takes Big O of k times log n. Now, the merge function, also like the one we wrote earlier, takes linear time, so that one is good; that one runs in the expected amount of time. So here we'll say, runs in linear time, and that would bring our overall runtime – so up at the mergeSort function, we can say this runs in Big O of k n times log n. It's okay, though; this is a…

Good start. And one day, when we talk about constant factors and look at ways we can reduce the cost of these operations using different strategies, we can come back and re-evaluate our code to improve our implementation. For now, as long as you understand how merge sort works conceptually, what the run time and space complexities look like, and where the bottlenecks are in your code, that's plenty of stuff. If you're interested in learning more about how we would solve this problem, check out the notes in the teacher's video.

In the next video, let's wrap this course up. And with that, let's wrap up this course. In the prerequisite to this course, Introduction to Algorithms, we learned about basic algorithms along with some concepts like recursion and Big O that set the foundation for learning about implementing and evaluating algorithms. In this course, we learned what a data structure is and how data structures go hand in hand with algorithms. We started off by exploring a data structure that many of us use in our day-to-day programming: arrays, or lists as they are known in Python. We take a peek under the hood at how arrays are created and stored and examine some of the common operations carried out on arrays. These are operations that we write and execute all the time, but here we took a step back and evaluated the run times of these operations and how they affect the performance of our code.

After that, we jumped into an entirely new world where we wrote our own data structure: a singly linked list. Admittedly, linked lists aren't used much in day-to-day problem solving, but it is a good data structure to start off with because it is fairly straightforward to understand and not that much different from an array. We carried out the same exercise as we did on arrays in that we looked at common data operations, but since this was a type we defined on our own, we implemented these operations ourselves and got to examine with a fine-tooth comb how our code and the structure of the type affected the runtime of these operations.

The next topic we tackled was essentially worlds colliding: we implemented a sorting algorithm to sort two different data structures. Here we got to see how all of the concepts we've learned so far—algorithmic thinking, time and space complexity, and data structures—all come together to tackle the problem of sorting data. This kind of exercise is one we're going to focus on moving forward as we try to solve more real-world programming problems using different data structures and algorithms.

If you've stuck with this content so far, keep up the great work. This can be a complex topic, but a really interesting one, and if you take your time with it, you will get a deeper understanding of programming and problem solving. As always, check the notes for more resources and happy coding. [Music]

You may have heard that algorithms and computer science are boring or frustrating. They certainly can be hard to figure out, especially the way some textbooks explain them, but once you understand what's going on, algorithms can seem fascinating, clever, or even magical. To help further your understanding of algorithms, this course is going to look at two categories: sorting algorithms and searching algorithms. You could argue that these are the easiest kinds of algorithms to learn, but in learning how these algorithms are designed, we'll cover useful concepts like recursion and divide and conquer that are used in many other sorts of algorithms and can even be used to create brand new ones. By the way, all the code samples I'm going to show in the videos will be in Python because it's a popular language that's relatively easy to read, but you don't need to know Python to benefit from this course. You can see the teacher's notes for each video for info on implementing these algorithms in your own favorite language.

Our goal with this course is to give you an overview of how sorting and searching algorithms work, but many algorithms have details that can be handled in different ways. Some of these details may distract from the big picture, so we've put them in the teacher's notes instead. You don't need to worry about these when completing the course for the first time, but if you're going back and referring to it later, be sure to check the teacher's notes for additional info.

Suppose we have a list of names. It's a pretty big list—a hundred thousand names long. This list could be part of an address book or social media app, and we need to find the locations of individual names within the list, possibly to look up additional data that's connected to the name. Let's assume there's no existing function in our programming language to do this, or that the existing function doesn't suit our purpose in some way. For an unsorted list, our only option may be to use linear search, also known as sequential search. Linear search is covered in more detail elsewhere on our site; check the teacher's notes for a link if you want more details. You start at the first element; you compare it to the value you're searching for. If it's a match, you return it; if not, you go to the next element. You compare that to your target; if it's a match, you return it; if not, you go to the next element, and so on through the whole list. The problem with this is that you have to search the entire list every single time. We're not doing anything to narrow down the search; each time we have to search all of it. If you're searching a big list or searching it repeatedly, this amount of time can slow your whole app down to the point that people may not want to use it anymore. That's why it's much more common to use a different algorithm for searching lists: binary search. Binary search is also covered in more detail elsewhere on our site; check the teacher's notes for a link. Binary search does narrow the search down for us; specifically, it lets us get rid of half the remaining items we need to search through each time. It does this by requiring that the list of values be sorted. It looks at the value in the middle of the list. If the value it finds is greater than the target value, it ignores all values after the value it's looking at. If the value it finds is less than the target value, it ignores all values before the value it's looking at. Then it takes the set of values that remain and looks at the value in the middle of that list again. If the value it finds is greater than the target value, it ignores all values after the value it's looking at. If the value it finds is less than the target value, it ignores all values before the value it's looking at. But as we mentioned, binary search requires the list of values you're searching through to be sorted. If the lists weren't sorted, you would have no idea which half of the values to ignore because either half could contain the value you're looking for; you'd have no choice but to use linear search. So before we can use binary search on a list, we need to be able to sort that list. We'll look at how to do that next.

Our end goal is to sort a list of names, but comparing numbers is a little easier than comparing strings, so we're going to start by sorting a list of numbers. I'll show you how to modify our examples to sort strings at the end of the course. To help make clear the importance of choosing a good sorting algorithm, we're going to start with a bad one: it's called Bogosort. Basically, Bogosort just randomizes the order of the list repeatedly until it's sorted. Here's a Python code file where we're going to implement Bogosort. It's not important to understand this code here at the top, although we'll have info on it in the teacher's notes if you really want it. All you need to know is that it takes the name of a file that we pass on the command line, loads it, and returns a Python list, which is just like an array in other languages, containing all the numbers that it read from the file. Let me have the program print out the list of numbers it loads so you can see it. We'll call the print method and we'll pass it the list of numbers. Save that. Let's run it real quick with `python bogosort.py`. Oh, whoops, and we need to provide it the name of the file here on the command line that we're going to load, so it's in the numbers directory; a slash separates the directory name from the file name: `five.txt`. And there's our list of numbers that was loaded from the file. Okay, let me delete that print statement, and then we'll move on. Bogosort just randomly rearranges the list of values over and over, so the first thing we're going to need is a function to detect when the list is sorted. We'll write an `is_sorted` function that takes a list of values as a parameter; it'll return `true` if the list passed in is sorted, or `false` if it isn't. We'll loop through the numeric index of each value in the list from 0 to 1 less than the length of the list. Like many languages, Python list indexes begin at 0, so a list with a length of 5 has indexes going from 0 through 4. If the list is sorted, then every value in it will be less than the one that comes after it, so we test to see whether the current item is greater than the one that follows it. If it is, it means the whole list is not sorted, so we can return `false`. If we get down here, it means the loop completed without finding any unsorted values. Python uses whitespace to mark code blocks, so unindenting the code like this marks the end of the loop. Since all the values are sorted, we can return `true`.

Now we need to write the function that will actually do the so-called sorting. The `bogosort` function will also take the list of values it's working with as a parameter. We'll call our `is_sorted` function to test whether the list is sorted. We'll keep looping until `is_sorted` returns `true`. Python has a ready-made function that randomizes the order of elements in the list. Since the list isn't sorted, we'll call that function here, and since this is inside the loop, it'll be randomized over and over until our `is_sorted` function returns `true`. If the loop exits, it means `is_sorted` returned `true`, and the list is sorted, so we can now return the sorted list. Finally, we need to call our `bogosort` function, pass it the list we loaded from the file, and print the sorted list it returns. Okay, let's save this and try running it. We do so with `python` the name of the script `bogosort.py` and the name of the file we're going to run it on: `numbers/five.txt`. It looks like it's sorting our list successfully, but how efficient is this? Let's add some code to track the number of times it attempts to sort the list. Up here at the top of the `bogosort` function, we'll add a variable to track the number of attempts it's made; we'll name it `attempts`, and we'll set its initial value to zero since we haven't made any attempts yet. With each pass through the loop, we'll print the current number of attempts, and then here at the end of the loop, after attempting to shuffle the values, we'll add one to the count of attempts. Let's save this and let's try running it again a couple of times in the console. I can just press the up arrow to bring up the previous command and re-run it, so it looks like this first run to sort this five-element list took 363 attempts. Let's try it again; this time it only took 91 attempts. We're simply randomizing the list with each attempt, so each run of the program takes a random number of attempts. Now let's try this same program with a larger number of items: `python bogosort.py numbers/eight.txt`. I have a list of eight items set up here in this other file. This time it takes 11,000 attempts, only 487 this time, and this time 13,000. You can see that the trend is increasing steadily. The problem with Bogosort is that it doesn't make any progress toward a solution with each pass. It could generate a list where just one value is out of order, but then on the next attempt it could generate a list where all the elements are out of order again. Stumbling on a solution is literally a matter of luck, and for lists with more than a few items, it might never happen. Up next we'll look at Selection Sort; it's a sorting algorithm that's still slow, but it's better than Bogosort.

Previously, we showed you Bogosort, a terrible sorting algorithm that basically randomizes the order of a list and then checks to see if it happens to be sorted. The problem with Bogosort is that it doesn't get any closer to a solution with each operation, and so with lists that have more than a few items, it'll probably never finish sorting them. Now we're going to look at an algorithm named Selection Sort. It's still slow, but at least each pass through the list brings it a little closer to completion. Our implementation of Selection Sort is going to use two arrays: an unsorted array and a sorted one. Some versions move values around within just one array, but we're using two arrays to keep the code simpler. The sorted list starts out empty, but we'll be moving values from the unsorted list to the sorted list one at a time. With each pass, we'll look through each of the values in the unsorted array, find the smallest one, and move that to the end of the sorted array. We'll start with the first value in the unsorted array and say that's the minimum, or smallest value we've seen so far. Then we'll look at the next value and see if that's smaller than the current minimum; if it is, we'll mark that as the new minimum. Then we'll move to the next value and compare that to the minimum again; if it's smaller, that becomes the new minimum. We continue that way until we reach the end of the list. At that point, we know whatever value we have marked as the minimum is the smallest value in the whole list. Now here's the part that makes Selection Sort better than Bogosort: we then move that minimum value from the unsorted list to the end of the sorted list. The minimum value isn't part of the unsorted list anymore, so we don't have to waste time looking at it anymore; all our remaining comparisons will be on the remaining values in the unsorted list. Then we start the process over. At this point, our list consists of the numbers 8, 5, 4, and 7. Our first minimum is 8. We start by comparing the minimum to 5; 5 is smaller than 8, so 5 becomes the new minimum. Then we compare 5 to 4, and 4 becomes the new minimum. 4 is not smaller than 7 though, so 4 remains the minimum. 4 gets moved to the end of the sorted array, becoming its second element. The process repeats again. 8 is the first minimum, but 5 is smaller, so that becomes the minimum. 7 is larger, so 5 stays as the minimum, and 5 is what gets moved over to the sorted array, and so on until there are no more items left in the unsorted array, and all we have left is the sorted array. So that's how Selection Sort works in general. Now let's do an actual implementation of it. This code here at the top is the same as we saw in the Bogosort example; it just loads a Python list of numbers from a file. Let's implement the function that will do our Selection Sort. We're going to pass in our Python list containing all the unsorted numbers. We'll create an empty list that will hold all our sorted values. We'll loop once for each value in the list. We call a function named `index_submin`, which we're going to write in just a minute, that finds the minimum value in the unsorted list and returns its index. Then we call the `pop` method on the list and pass it the index of the minimum value; `pop` will remove that item from the list and return it. We then add that value to the end of the sorted list. Going up a level of indentation signals to Python that we're ending the loop. After the loop finishes, we return the sorted list. Now we need to write the function that picks out the minimum value. We pass in the list we're going to search. We mark the first value in the list as the minimum; it may or may not be the actual minimum, but it's the smallest we've seen on this pass through the list; it's also the only value we've seen on this pass through the list so far. Now we loop through the remaining values in the list after the first. We test whether the value we're currently looking at is less than the previously recorded minimum; if it is, then we set the current index as the new index of the minimum value. After we've looped through all the values, we return the index of the smallest value we found. Lastly, we need to actually run our Selection Sort method and print the sorted list it returns. Let's save this and now let's try running it. We run the `python` command and pass it the name of our script `selectionsort.py`. In the numbers directory, I've saved several data files filled with random numbers, one on each line: `five.txt` has five lines, `eight.txt` has eight lines, and to help us really measure the speed of our algorithms, `ten_thousand.txt` has ten thousand lines. I've even created a file with a million numbers. Our script takes the path of a file to load as an argument, so I'll give it the path of our file with five numbers: `numbers/five.txt`. The script runs, reads the numbers in the file into a list, calls our Selection Sort method with that list, and then prints the sorted list. Let me add a couple of print statements within the Selection Sort function so you can watch the sort happening. Don't worry about figuring out the Python formatting string that I use; it's just there to keep the two lists neatly aligned. I'll add the first print statement before the loop runs at all; I'll have it print out the unsorted list and the sorted list. I'll add an identical print statement within the loop so we can watch values moving from the unsorted list to the sorted list. Let's save this and we'll try running the same command again. The output looks like this. You can see the unsorted list on the left and the sorted list on the right. Initially, the sorted list is empty. On the first pass, it selects the lowest number, 1, and moves it to the sorted list. Then it moves the next lowest number over, 4. This repeats until all the numbers have been moved to the sorted list. I have another file with eight different numbers in it. Let's try our program with that: `python selectionsort.py numbers/eight.txt`. You can see the same process at work here. Notice that this file had some duplicate values too; that's okay though, because the `index_of_min` function only updates the minimum index if the current value is less than the previous minimum. If they're equal, it just keeps the first minimum value it found and waits to move the duplicate value over until the next pass through the list. So now we know that the Selection Sort algorithm works, but the datasets we've been giving it to sort are tiny. In the real world, algorithms need to work with datasets of tens of thousands or even millions of items, and do it fast. I have another file with ten thousand random numbers in it. Let's see if Selection Sort can handle that. If I run this as it is now though, it'll print out a lot of debug info as it sorts the list, so first I'm going to go into the program and remove the two print statements in the Selection Sort function. Now let's run the program again on the `.txt` file and see how long it takes: `python selectionsort.py numbers/ten_thousand.txt`. One, one thousand, two, one thousand, three, one thousand, four, one thousand, five, one thousand, six, one thousand, seven, one thousand, eight, one thousand, nine, one thousand, ten, one thousand, eleven thousand, twelve thousand, thirteen thousand... and it prints out all ten thousand of those numbers neatly sorted. It took a little bit though. How long? Well, counting the time off vocally isn't very precise, and other programs running on the system can skew the amount of time your program takes to complete. Let me show you a Unix command that's available here in workspaces which can help you. Type `time` followed by a space and then the command you want to run. So this command by itself will print the contents of our `five.txt` file: `cat numbers/five.txt`. And this command will do the same thing, but it'll also keep track of how long it takes the `cat` program to complete and report the result: `time cat numbers/five.txt`. The "real" row in the results is the actual amount of time from when the program started running to when it completed. We can see it finished in a fraction...

Of a second, but as we said, other programs running on the system can take CPU resources, in which case your program will seem slower than it is. So we generally want to ignore the real result. The user result is the amount of time the CPU actually spent running the program code; so this is the total amount of time the code inside the cat program took to run. The sys result is the amount of time the CPU spent running Linux kernel calls that your code made. The Linux kernel is responsible for things like network communications and reading files, so loading the 5.txt file is probably included in this result. In evaluating code's performance, we're generally going to want to add together the user and sys results, but `cat` is a very simple program. Let's try running the `time` command on our code and see if we get a more interesting result.

`time python selection_sort.pi numbers_ten_thousand.txt`

This takes much longer to complete—nearly 12 seconds according to the real-time measurement—but as we said, the real result is often skewed, so let's disregard that. If we add the user and sys runtimes together, we get about 6 seconds. The time for the program to complete will vary a little bit each time you run it, but if it's doing the same operations, it usually won't change more than a fraction of a second. If I run our selection sort script on the same file, you can see it completes in roughly the same time.

Now let's try it on another file with 1 million numbers:

`time python selection_sort.pi numbers_1_million.txt`

How long does this one take? I don't even know. While designing this course, I tried running this command and my workspace connection timed out before it completed. So we'll just say that selection sort takes a very, very long time to sort a million numbers. If we're going to sort a list that big, we're going to need a faster algorithm. We'll look into alternative sorting algorithms shortly.

The next two sorting algorithms we look at will rely on recursion, which is the ability of a function to call itself. So before we move on, we need to show you how recursion works. Recursive functions can be very tricky to understand. Imagine a row of dominoes stood on end, where one domino falling over causes the next domino to fall over, which causes the next domino to fall over, causing a chain reaction. It's kind of like that.

Let's suppose we need to write a function that adds together all the numbers in an array, or in the case of Python, a list. Normally, we'd probably use a loop for this sort of operation. The function takes a list of the numbers we want to add; the total starts at zero; we loop over every number contained in the list, and we add the current number to the total. Once we're done looping, we return the accumulated total. If we call this `sum` function with a list of numbers, it'll return the total. When we run this program, it'll print out that return value, 19. Let's try it real quick:

`python recursion.pi`

Oh, whoops! Mustn't forget to save my work here and run it, and we see the result 19.

To demonstrate how recursion works, let's revise the `sum` function to use recursion instead. Note that recursion is not the most efficient way to add a list of numbers together, but this is a good problem to use to demonstrate recursion because it's so simple. One thing before I show you the recursive version, though: this example is going to use the Python slice syntax, so I need to take a moment to explain that for those not familiar with it. A slice is a way to get a series of values from a list. Let's load up the Python REPL, or read-evaluate-print loop, so I can demonstrate. We'll start by creating a list of numbers to work with:

`numbers = [0, 1, 2, 3, 4]`

Containing those numbers, like arrays in most other languages, Python list indexes start at 0, so `numbers[1]` will actually get the second item from the list. With slice notation, I can actually get several items back. It looks just like accessing an individual index of a list, but then I type a colon followed by the list index that I want up to, but not including. So `numbers[1:4]` would get us the second up to, but not including, the fifth items from the list; that is, it'll get us the second through the fourth items. Now I know what you're thinking, and you're right—that up-to-but-not-including rule is a little counterintuitive—but you can just forget all about it for now because we won't be using a second index with any of our Python slice operations in this course. Here's what we will be using: when you leave the second index off of a Python slice, it gives you the items from the first index up through the end of the list, wherever that is. So `numbers[1:]` will give us items from the second index up through the end of the list; `numbers[2:]` will give us items from the third index up to the end of the list. You can also leave the first index off to get everything from the beginning of the list; `numbers[:3]` will get us everything from the beginning of the list up to, but not including, the third index. It's also worth noting that if you take a list with only one item and you try to get everything from the non-existent second item onwards, the result will be an empty list. So if I create a list with just one item in it and I try to access from the second element onwards—the second element doesn't exist—so the result will be an empty list. Don't worry too much about remembering Python slice syntax; it's not an essential part of sorting algorithms or recursion. I'm only explaining it to help you read the code you're about to see. So I'm going to exit the Python REPL now.

That we've covered recursion, we can convert our `sum` function to a recursive function. It'll take the list of numbers to add, just like before. Now here's the recursive part: we'll have the `sum` function call itself. We use slice notation to pass the entire list of numbers except the first one; then we add the first number in the list to the result of the recursive function call and return the result. So if we call `sum` with four numbers first, it'll call itself with the remaining three numbers; that call to `sum` will then call itself with the remaining two numbers, and so on. But if we save this and try to run it:

`python recursion.pi`

Well, first we get a syntax error. It looks like I accidentally indented something I shouldn't have, so let me go fix that real quick. There we go. That's suggested to Python that there was a loop or something there when there wasn't. So let's go back to the terminal and try running this again. There we go. Now we're getting the error I was expecting: `RecursionError: maximum recursion depth exceeded`. This happens because `sum` gets into an infinite loop; it keeps calling itself over and over. The reason is that when we get down to a list of just one element and we take a slice from the non-existent second element to the end, the result is an empty list. That empty list gets passed to the recursive call to `sum`, which passes an empty list in its recursive call to `sum`, and so on, until the Python interpreter detects too many recursive calls and shuts the program down. What we need is to add a base case to this recursive function—a condition where the recursion stops. This will keep it from getting into an infinite loop. With the `sum` function, the base case is when there are no elements left in the list; in that case, there is nothing left to add, and the recursion can stop. A base case is the alternative to a recursive case—a condition where recursion should occur. For the `sum` function, the recursive case is when there are still elements in the list to add together. Let's add a base case at the top of the function. Python treats a list that contains one or more values as a true value, and it treats a list containing no values as a false value. So we'll add an `if` statement that says if there are no numbers in the list, we should return a sum of zero. That way, the function will exit immediately without making any further recursive calls to itself. We'll leave the code for the recursive case unchanged; if there are still numbers in the list, the function will call itself with any numbers after the first, then add the return value to the first number in the list. Let's save this and try running it again:

`python recursion.pi`

Output: the sum of the numbers in the list, 19. But it's still not really clear how this worked. Let's add a couple `print` statements that will show us what it's doing. We'll show the recursive call to `sum` and what it's being called with. We'll also add a call to `print` right before we return, showing which of the calls the `sum` is returning and what it's returning. Let me save this and resize the console a bit, and let's try running it again:

`python recursion.pi`

Since the `print` calls are inside the `sum` function, the first call to `sum` (1, 2, 7, 9) isn't shown; only the recursive calls are. This first call to `sum` ignores the first item in the list (1) and calls itself recursively; it passes the remaining items from the list (2, 7, and 9). That call to `sum` again ignores the first item in the list it receives (2) and again calls itself recursively; it passes the remaining items in the list (7 and 9). That call ignores the 7 and calls itself with a 9; and the last call shown here ignores the 9 and calls itself with an empty list. At this point, none of our recursive calls to `sum` have returned yet; each of them is waiting on the recursive call it made to `sum` to complete. Python and other programming languages use something called a call stack to keep track of this series of function calls; each function call is added to the stack along with the place in the code that it needs to return when it completes. But now the empty list triggers the base case, causing the recursion to end and the `sum` function to return zero. That zero value is returned to its caller; the caller adds the zero to the first and only value in its list (9); the result is 9. That nine value gets returned to the caller, which adds it to the first value in the list it received (7); the result is 16. That 16 value is returned to the caller, which adds it to the first value in the list it received (2); the result is 18. That 18 value is returned to the caller, which adds it to the first value in the list it received (1); the result is 19. That 19 value is returned to the caller, which is not the `sum` function recursively calling itself, but our main program. This is our final result, which gets printed. It's the same result we got from the loop-based version of our program. The end. We don't want the `print` statements in our final version of the program, so let me just delete those real quick, and there you have it: a very simple recursive function. Well, the function is simple, but as you can see, the flow of control is very complex. Don't worry if you didn't understand every detail here because we won't be using this particular example again. There are two fundamental mechanisms you need to remember: a recursive function needs a recursive case that causes it to call itself, and it also needs to eventually reach a base case that causes the recursion to stop.

You've seen bogosort, which doesn't make any progress towards sorting a list with each pass; either it's entirely sorted or it isn't. You've seen selection sort, which moves one value over to a sorted list with each pass so that it has fewer items to compare each time. Now let's look at an algorithm that speeds up the process further by further reducing the number of comparisons it makes; it's called quicksort. Here's some Python code where we'll implement quicksort. Again, you can ignore these lines at the top; we're just using them to load a file full of numbers into a list. The quicksort algorithm relies on recursion to implement it. We'll write a recursive function; we'll accept the list of numbers to sort as a parameter. Quicksort is recursive because it keeps calling itself with smaller and smaller subsets of the list you're trying to sort. We're going to need a base case where the recursion stops so it doesn't enter an infinite loop. Lists that are empty don't need to be sorted, and lists with just one element don't need to be sorted either; in both cases, there's nothing to flip around, so we'll make that our base case. If there are zero or one elements in the list passed to the quicksort function, we'll return the unaltered list to the caller. Lastly, we need to call our quicksort function with our list of numbers and print the list it returns. That takes care of our base case. Now we need a recursive case. We're going to rely on a technique that's common in algorithm design called divide and conquer; basically, we're going to take our problem and split it into smaller and smaller problems until they're easy to solve. In this case, that means taking our list and splitting it into smaller lists.

Viewer suggestion: The process I'm about to describe is complex; there's just no way around it. If you're having trouble following along, remember the video playback controls; feel free to slow the playback down, rewind, or pause the video as needed after you watch this the first time. You may also find it helpful to rewind and make your own diagram of the process as we go. Okay, ready? Here goes. Suppose we load the numbers from our 8.txt file into a list. How do we divide it? It would probably be smart to have our quicksort function divide the list in a way that brings it closer to being sorted. Let's pick an item from the list; we'll just pick the first item for now (4). We'll call this value we've picked the pivot, like the center of a seesaw on a playground. We'll break the list into two sublists: the first sublist will contain all the items in the original list that are smaller than the pivot; the second sublist will contain all the items in the original list that are greater than the pivot. The sublist of values less than and greater than the pivot aren't sorted, but what if they were? You could just join the sublists and the pivot all together into one list, and the whole thing would be sorted. So how do we sort the sublist? We call our quicksort function recursively on them. This may seem like magic, but it's not; it's the divide and conquer algorithm design technique at work. If our quicksort function works on the big list, then it will work on the smaller list too. For our first sublist, we take the first item; it's the pivot again (that's 3). We break the sublist into two sublists: one with everything less than the pivot and one with everything greater than the pivot. Notice that there's a value equal to the pivot that gets put into the less-than sublist. Our finished quicksort function is actually going to put everything that's less than or equal to the pivot in the first sublist, but I don't want to say less than or equal to over and over, so I'm just referring to it as the less-than-pivot sublist. Also notice that there are no values greater than the pivot; that's okay. When we join the sublists back together, that just means nothing will be in the return list after the pivot. We still have one sublist that's more than one element long, so we call our quicksort function on that too. You and I can see that it's already sorted, but the computer doesn't know that, so it'll call it anyway, just in case. It picks the first element (2) as a pivot; there are no elements less than the pivot and only one element greater than the pivot. That's it for the recursive case; we've finally hit the base case for our quicksort function. It'll be called on both the empty list of elements less than the pivot and the one-item list of elements greater than the pivot, but both of these lists will be returned as they are because there's nothing to sort. So now, at the level of the call stack above this, the return sorted lists are used in place of the unsorted sublist that's less than the pivot and the unsorted sublist that's greater than the pivot; these are joined together into one sorted list. Remember that any empty lists get discarded. Then, at the level of the call stack above that, the return sorted lists are used in place of the unsorted sublists there again; they were already sorted, but the quicksort method was called on them anyway, just in case. The sublists are joined together into one sorted list. At the level of the call stack above that, the return sorted list is used in place of the unsorted sublist that's less than the pivot, so now everything that's less than or equal to the pivot is sorted. Now we call quicksort on the unsorted sublist that's greater than the pivot, and the process repeats for that sublist. We pick the first element (6) as the pivot; we split the sublist into sublists of elements that are less than and greater than this pivot, and we recursively call the quicksort function until those sublists are sorted. Eventually, a sorted sublist is returned to our first quicksort function call; we combine the sublist that's less than or equal to the pivot, the pivot itself, and the sublist that's greater than the pivot into a single list, and because we recursively sorted the sublists, the whole list is sorted. So that's how the quicksort function is going to work. In the next video, we'll show you the actual code.

Quicksort works by picking a pivot value, then splitting the full list into two sublists: the first sublist has all the values less than or equal to the pivot, and the second sublist has all the values greater than the pivot. The quicksort function recursively calls itself to sort these sublists and then to sort the sublists of those sublists until the full list is sorted. Now it's time to actually implement this in code. We already have the base case written; any list passed in that consists of 0 or 1 values will be returned as is because there's nothing to sort. Now we need to create a list that will hold all the values less than the pivot; that list will be empty at first. We do the same for values greater than the pivot. Next, we need to choose the pivot value; for now, we just grab the first item from the list. Then we loop through all the items in the list following the pivot; we check to see whether the current value is less than or equal to the pivot; if it is, we copy it to the sublist of values less than the pivot; otherwise, the current value must be greater than the pivot, so we copy it to the other list. This last line is where the recursive magic happens: we call quicksort recursively on the sublist that's less than the pivot; we do the same for the sublist that's greater than the pivot. Those two calls will return sorted lists, so we combine the sort of values less than the pivot, the pivot itself, and the sort of values greater than the pivot; that gives us a complete sorted list, which we return. This took a lot of prep work. Are you ready? Let's try running it:

`python quicksort.pi numbers_8.txt`

It outputs our sorted list. I don't know about you, but this whole thing still seems a little too magical to me. Let's add a couple `print` statements to the program so we can see what it's doing. First, we'll add a `print` statement right before the first call to the quicksort function so we can see the unsorted list. We'll also add a `print` right within the quicksort function, right before the recursive calls. Again, this string formatting code is just to keep the info aligned in columns. Let's try running this again, and now you can see our new debug output. Each time quicksort goes to call itself recursively, it prints out the pivot as well as the sublist of items less than or equal to the pivot, if any, and the sublist of items greater than the pivot, if any. You can see that first it sorts the sublist of items less than the pivot at the top level; it goes through a couple levels of recursion to do that. There are actually additional levels of recursion, but they're from calls to quicksort with a list of 0 or 1 elements, and those calls return before the `print` statement is reached. Then it starts sorting the second sublist from the top level with items greater than the original pivot; you can see a couple levels of recursion for that.

Sort as well. Finally, when both sublists are recursively sorted, the original call to the quicksort function returns, and we get the sorted list back. So we know that it works. The next question is how well does it work? Let's go back to our file of ten thousand numbers and see if it can sort those. First, though, I'm going to remove our two debug calls to print, so it doesn't produce unreadable output. A quick note: if you try running this on a file with a lot of repeated values, it's possible you'll get a runtime error: maximum recursion depth exceeded. If you do, see the teacher's notes for a possible solution.

Now let's try running our quick sort program against the ten thousand.text file: python quick_sort.pi numbers_10_000.text. There we go, and it seems pretty fast, but how fast exactly? Let's run it with the time command to see how long it takes: time python quick_sort.pi numbers_10_000.text. Remember, we need to ignore the real result and add the user and sys results. It took less than a second of CPU time to sort 10,000 numbers with quicksort. Remember that selection sort took about 13 seconds. That's a pretty substantial improvement. And with a million numbers, selection sort took so long that it never even finished successfully. Let's see if quicksort performs any better: time python quick_sort.pi numbers_1_million.text. Not only did quicksort sort a million numbers successfully, it only took about 11 seconds of CPU time. Quicksort is clearly much, much faster than selection sort. How much faster? That's something we'll discuss in a later video. What we've shown you here is just one way to implement quicksort. Although the basic algorithm is always the same, the details can vary, like how you pick the pivot. See the teacher's notes for more details.

Let's review another sorting algorithm: merge sort, so that we can compare it with quick sort. Merge sort is already covered elsewhere on the site, so we won't go into as much detail about it, but we'll have more info in the teacher's notes if you want it. Both quicksort and merge sort are recursive. The difference between them is in the sorting mechanism itself. Whereas quicksort sorts a list into two sub-lists that are less than or greater than a pivot value, merge sort simply splits the list in half recursively and then sorts the halves as it merges them back together. That's why it's called merge sort.

You may recognize this code at the top by now; it just loads a file full of numbers into a list. Let's define a recursive merge sort function. As usual, it'll take the list or sub-list that we want it to sort. Our base case is the same as with quicksort: if the list has zero or one values, there's nothing to sort, so we return it as is. If we didn't return it, means we're in the recursive case. So first, we need to split the list in half. We need to know the index we should split on, so we get the length of the list and divide it by two. So, for example, if there are eight items in the list, we'll want an index of four. But what if there were an odd number of items in the list, like seven? We can't have an index of 3.5, so we'll need to round down. In that case, since we're working in Python currently, we can take advantage of a special Python operator that divides and rounds the result down: the floor division operator. It consists of a double slash. Now we'll use the Python slice syntax to get the left half of the list. We'll pass that list to a recursive call to the merge sort function. We'll also use slice syntax to get the right half of the list and pass that to merge sort as well.

Now we need to merge the two halves together and sort them as we do it. We'll create a list to hold the sorted values. And now we get to the complicated part: merging the two halves together and sorted them as we do it. We'll be moving from left to right through the left half of the list, copying values over to the sorted values list as we go. This left index variable will help us keep track of our position. At the same time, we'll also be moving from left to right through the right half of the list and copying values over, so we need a separate right index variable to track that position as well. We'll keep looping until we've processed all of the values in both halves of the list. We're looking to copy over the lowest values first, so first we test whether the current value on the left side is less than the value on the right side. If the left side value is less, that's what we'll copy over to the sorted list, and then we'll move to the next value in the left half of the list. Otherwise, the current value from the right half must have been lower, so we'll copy that value to the sorted list instead, and then we'll move to the next value in the right half of the list. That ends the loop. At this point, one of the two unsorted halves still has a value remaining, and the other is empty. We won't waste time checking which is which; we'll just copy the remainder of both lists over to the sorted list. The one with the value left will add that value, and the empty one will add nothing. All the numbers from both halves should now be copied to the sorted list, so we can return it. Finally, we need to kick the whole process off. We'll call the merge sort function with the list of numbers we loaded and print the result. Let's save this, and we'll try it out on our file with eight numbers: python merge_sort.pi numbers_eight.text. And it prints out the sorted list. But again, this seems pretty magical. Let's add some print statements to get some insight into what it's doing. First, we'll print the unsorted list so we can refer to it. We'll add a print statement right before we call the merge sort function for the first time. Then we'll add another print statement within the merge sort function right after the recursive calls. This will show us the sorted left half and right half that it's returning. Again, don't worry about the fancy Python formatting string; it just keeps the values neatly aligned. Let me resize my console, clear the screen, and then we'll try running this again. What we're seeing are the values being returned from the recursive merge sort function calls, not the original calls to merge sort. So what you see here is after we reach the base case with a list that's only one item in length, and the recursive calls start returning, the original list gets split into two unsorted halves: four, six, three, and two, and nine, seven, three, and five. The first half gets split in half again: four and six, and three and two. And each of those halves is halved again into single element lists. There's nothing to sort in the single element list, so they're returned from the merge sort function as is. Those single element lists get merged into two sub-lists and sorted as they do so. The four and six sub-list looks the same after sorting as it did before sorting, but the three and the two get sorted as they're combined into a sub-list. The new order is two, three. The order is shifted again when those two sub-lists get combined back into a single list: two, three, four, six. Then we recursively sort the right half of the original list: nine, seven, three, five. It gets split in half again: nine, seven, and three, five. And each of those halves get broken into single element lists. There's nothing to sort there, so the single element lists are returned as is. The first two are sorted as they're merged: seven, nine, and so are the second: three, five. And then those two sub-lists get sorted as they're combined into another sub-list: three, five, seven, nine. And finally, everything is sorted as it's merged back into the full sorted list: two, three, three, four, five, six, seven, nine. That's how merge sort works on a list of eight numbers. Let's see if it works on a bigger list. First, I'll remove the two print statements so we don't get an overwhelming amount of debug output. Then I'll run it on a list of ten thousand items: python merge_sort.pi numbers_ten_thousand.text. Not only did it work, it was pretty fast. But which is faster: merge sort or quick sort? We'll look at that next. I've removed the call to print that displays the sorted list at the end of our selection sort, quick sort, and merge sort scripts. That way, it'll still run the sort, but the output won't get in the way of our comparing runtimes. Let's try running each of these scripts and see how long it takes: time python selection_sort. We'll do that one first: numbers_10_000.text. We combine the user and sys results, and that gives us about six seconds. Now let's try quick sort: time python quick_sort.pi numbers_10_000.text. Much faster: less than a second. And finally: time python merge_sort.pi numbers_10_000.text. A little longer, but far less than a second. So even on a list with just 10,000 numbers, selection sort takes many times as long as quicksort and merge sort. And remember, I ran the selection sort script on a file with a million numbers, and it took so long that my workspace timed out before it completed. It looks like selection sort is out of the running as a viable sorting algorithm. It may be easy to understand and implement, but it's just too slow to handle the huge data sets that are out in the real world.

Now let's try quicksort and merge sort on our file with a million numbers and see how they compare there: time python quicksort.pi numbers_million.text. Looks like it took about 11 seconds of CPU time. Now let's try merge sort: time python merge_sort.pi numbers_1_million.text. That took about 15 seconds of CPU time. It looks like quicksort is marginally faster than merge sort on this sample data. We had to learn a lot of details for each algorithm we've covered in this course. Developers who need to implement their own algorithms often need to choose an algorithm for each and every problem they need to solve, and they often need to discuss their decisions with other developers. Can you imagine needing to describe all the algorithms in this same level of detail all the time? You'd spend all your time in meetings rather than programming. That's why Big O notation was created as a way of quickly describing how an algorithm performs as the data set it's working on increases in size. Big O notation lets you quickly compare several algorithms to choose the best one for your problem. The algorithms we've discussed in this course are very well known. Some job interviewers are going to expect you to know their Big O run times, so let's look at them. Remember that the n in Big O notation refers to the number of elements you're operating on. With selection sort, you need to check each item in the list to see if it's the lowest, so you can move it over to the sorted list. So that's n operations. Suppose you're doing selection sort on a list of five items, and in this case, n would be five. So that's five operations before you can move an item to the sorted list. But with selection sort, you have to loop over the entire list for each item you want to move. There are five items in the list, and you have to do five comparisons to move each one, so it's more like 5 times 5 operations. Or if we replace 5 with n, it's n times n, or n squared. But wait, you might say: half of that 5 by 5 grid of operations is missing because we're testing one fewer item in the unsorted list with each pass. So isn't it more like one half times n times n? And this is true; we're not doing a full n squared operations. But remember, in Big O notation, as the value of n gets really big, constants like one half become insignificant, and so we discard them. The Big O runtime of selection sort is widely recognized as being O(n squared).

Quicksort requires one operation for each element of the list it's sorting. It needs to select a pivot first, and then it needs to sort elements into lists that are less than or greater than the pivot. So that's n operations. To put that another way, if you have a list of eight items, then n is eight, so it will take eight operations to split the list around the pivot. But of course, the list isn't sorted after splitting it around the pivot just once. You have to repeat those eight operations several times. In the best case, you'll pick a pivot that's right in the middle of the list, so that you're dividing the list exactly in half. Then you keep dividing the list in half until you have a list with a length of one. The number of times you need to divide n in half until you reach one is expressed as log n. So you need to repeat n sorting operations log n times. That leaves us with the best-case run time for quick sort of O(n log n). But that's the best case. What about the worst case? Well, if you pick the wrong pivot, you won't be dividing the list exactly in half. If you pick a really bad pivot, the next recursive call to quicksort will only reduce the list length by one. Since our quicksort function simply picks the first item to use as a pivot, we can make it pick the worst possible pivot repeatedly simply by giving it a list that's sorted in reverse order. If we pick the worst possible pivot every time, we'll have to split the list once for every item it contains and then do n sorting operations on it. You already know another sorting algorithm that only manages to reduce the list by one element with each pass: selection sort. Selection sort has a runtime of O(n squared), and in the worst case, that's the run time for quicksort as well. So which do we consider when trying to decide whether to use quicksort: the best case or the worst case? Well, as long as your implementation doesn't just pick the first item as a pivot, which we did so we could demonstrate this issue, it turns out that on average, quicksort performs closer to the best case. Many quicksort implementations accomplish this simply by picking a pivot at random on each recursive loop. Here we are sorting our reverse sorted data again, but this time we pick pivots at random, which reduces the number of recursive operations needed. Sure, random pivots sometimes give you the best case, and sometimes you'll randomly get the worst case, but it all averages out over multiple calls to the quick sort function.

Now with merge sort, there's no pivot to pick. Your list of n items always gets divided in half log n times. That means merge sort always has a Big O runtime of O(n log n). Contrast that with quicksort, which only has a runtime of O(n log n) in the best case. In the worst case, quicksort's runtime is O(n squared), and yet out in the real world, quicksort is more commonly used than merge sort. Now why is that? If quicksort's Big O runtime can sometimes be worse than merge sort's? This is one of those situations where Big O notation doesn't tell you the whole story. All Big O can tell you is the number of times an operation is performed; it doesn't describe how long that operation takes. And the operation merge sort performs repeatedly takes longer than the operation quicksort performs repeatedly. Big-O is a useful tool for quickly describing how the runtime of an algorithm increases as the data set it's operating on gets really, really big, but you can't always choose between two algorithms based just on their Big O runtimes. Sometimes there's additional info you need to know about an algorithm to make a good decision. Now that we can sort a list of items, we're well on our way to being able to search a list efficiently as well. We'll look at how to do that in the next stage. [Music]

Now that we've covered sorting algorithms, the groundwork has been laid to talk about searching algorithms. If you need to search through an unsorted list of items, binary search isn't an option because you have no idea which half of the list contains the item you're looking for. Your only real option is to start at the beginning and compare each item in the list to your target value one at a time until you find the value you're looking for. This algorithm is called linear search or sequential search because the search proceeds in a straight line or sequence. Even though linear search is inefficient, searching for just one name will happen so fast that we won't be able to tell anything useful about the algorithm's runtime. So let's suppose we had a hundred different names and that we needed to know where they appear in a list of unsorted names. Here's some code that demonstrates. As usual, this code at the top isn't relevant to the search algorithm; it's just like the code that loaded a list of numbers from a file in the previous stage. But this code calls a different function, load_strings, that loads a list of strings in. If you want the load_strings Python code, we'll have it for you in the teacher's notes. Here's a separate hard-coded list containing the 100 names we're going to search for. We'll loop through each name in this list and pass it to our search function to get the index within the full list where it appears.

Now let's implement the search function. Compared to the sorting algorithms, this is going to be short. The index_of_item function takes the Python list you want to search through and a single target value you want to search for. Now we need to loop over each item in the list. The range function gives us a range of numbers from its first argument up to but not including its second argument. So if our list had a length of 5, this would loop over the indexes 0 through 4. We test whether the list item at the current index matches our target. If it does, then we return the index of the current item. This will exit the index_of_item function without looping over the remaining items in the list. If we reach the end of the loop without finding the target value, that means it wasn't in the list. So instead of returning an index, we return the special Python value None, which indicates the absence of a value. Other languages have similar values like nil or null, but if yours doesn't, you might have to return a value that would otherwise be impossible, like an index of negative 1. Now let's call our new search function. We start by looping over the list of 100 values we're looking for. We're using the values themselves this time, not their indexes within the list, so there's no need to mess with Python's range function. Here's the actual call to the index_of_item function. We pass it the full list of names that we loaded from the file plus the name we want to search for within that list. Then we store the index it returns in a variable, and lastly, we print the index we get back from the index_of_item function. Let's save this and go to our console and see if it works: python linear_search.pi names_unsorted.text. And it'll print out the list of indexes for each name. I actually set it up so that the last two items in the list of names we're going to search for corresponded to the first and last name within the file. So if we open up our unsorted.txt file, we'll see Mary Rosenberger is the first name, and Alonso Viviano is the last name, and those are the last two values in our list of names we're searching for. So it returned an index of zero for that second to last name, and you can see that name here on line one of the file. The line numbering starts at one, and the Python list indexes start at zero, so that makes sense. And for the last name, it returned an index of 109873, and you can see that name here on line 109874. So we can see that it's returning the correct indexes. But right now, we're just searching for a hundred different names in a list of one hundred thousand names. In the real world, we're going to be looking for many more names than that within much bigger lists than that. Can we do this any faster? Yes, but we'll need to use the binary search algorithm, and for that to work, we need to sort our list of strings. We'll do that in the next video. Before we can use the binary search algorithm on our list of names, we need to sort it. Let's do that now. We need to load our unsorted list of names from a file, sorted, and write the sorted names back out to a new file. Again, this code at the top just loads a

File full of strings into a list. We'll use our quick sort method to sort the list of names. Its code is completely unchanged from when you saw it in the previous stage. We just call our quick sort function on the list of names loaded from the file and save the list to a variable. Then we loop through each name in the sorted list, and we print that name. That's all there is to it.

Let's save this script and try running it: python quicksort_strings.py, and we'll pass it the names_unsorted.text file. Let me resize the console window here a little bit. That prints the sorted list of names out to the terminal, but we need it in a file. So we'll do what's called a redirect of the program's output. We'll run the same command as before, but at the end we'll put a greater than sign followed by the path to a file that we want the program output written to: names_sorted.text.

Redirecting works not only on Linux-based systems like workspaces, but also on Macs and even on Windows machines. You just need to be careful because if you redirect to an existing file, its contents will be overwritten without asking you. Let me refresh the list of files in the sidebar, and you'll see that we now have a new names_sorted.text file in the names directory. It's the same number of lines as the names_unsorted.text file, but all the names are sorted now. Now we can load this file of sorted names into a list, and we'll be able to use that list with the binary search algorithm. We'll see how to do that next.

Now that we have our list of names sorted, we can use the binary search algorithm on it. Let's see if we can use it to speed up our search for the indexes of 100 names. Binary search keeps narrowing down the list until it has the value it's looking for. It's faster than linear search because it discards half the potential matches each time. Our code here at the top of our binary search script is unchanged from the previous scripts. We just call the load_strings function to load our 100,000 sorted names from a file. Here we've hard-coded the list of 100 names we're going to search for. Again, it's identical to the list from the linear search script, except that I've again changed the last two names to correspond to the names on the first and last lines of the file we'll be loading.

Now let's write the function that will implement our binary search algorithm. Like the linear search function before, it'll take two arguments: the first is the list we're going to search through, and the second is the target value we'll be searching for. Again, the binary search function will return the index it found the value at, or the special value None if it wasn't found. Binary search is faster than a linear search because it discards half the values it has to search through each time. To do this, it needs to keep track of a range that it still needs to search through. To start, that range is going to include the full list. The first variable will track the lowest index in the range we're searching; to start, it's going to be 0, the first index in the full list. Likewise, the last variable will track the highest index in the range we're searching; to start, we'll set it to the highest index in the full list.

If the first and last variables are equal, then it means the size of the search range has shrunk to zero, and there is no match. Until that happens though, we'll keep looping. To continue the search, we want to divide the list of potential matches in half each time. To do that, we need to check the value that's in the middle of the range we're searching in. We add the indexes in the first and last variables, then divide by two to get their average. We might get a fractional number, which can't be used as a list index, so we also round down using Python's double slash floor division operator. All this will give us the index of the list element that's the midpoint of the range we're searching. We store that in the midpoint variable. Whoops, looks like my indentation got mixed up there. Let me fix that real quick. There we go.

Now we test whether the list element at the midpoint matches the target value. If it does, we return the midpoint index without looping any further; our search is complete. Otherwise, if the midpoint element's value is less than the target value, then we know that our target value can't be at the midpoint or any index prior to that, so we move the new start of our search range to just after the old midpoint. Otherwise, the midpoint element's value must have been greater than the target value. We know that our target value can't be at the midpoint or any index after that, so we move the new end of our search range to just before the old midpoint. By unindenting here, we mark the end of the loop. If the loop completes, it means the search range shrank to nothing without our finding a match, and that means there's no matching value in the list, so we return the special Python value None to indicate this.

Lastly, just as we did in our linear search script, we need to search for each of the 100 names. We loop over each name in our hard-coded list, and we call the binary search function with the sorted list of names we're going to load from the file and the current name we're searching for. We store the returned list index in the index variable, and finally we print that variable. Let's save this and go to our console and try running it: python binarysearch.py, and it's important to give it the name of the sorted file. If it loads the unsorted file, the binary search won't work, so names_sorted.text. Again, it prints out the list of indexes for each name. I once again set it up so the last two items in the list of names we're going to search for corresponded to the first and last name in the file, so it returned an index of 0 for the second to last name, and you can see that name here: Aaron Augustine. You can see that name here on line one of the file. And for the last name, it returned an index of 109873, and you can see that name here on line 109874. Let's check the third to last name for good measure. It looks like an index of 97022 was printed for that name: Stephen Daras. Let's search for Stephen Daras within the file, and here it is on line 97023. Remember that line numbers start on one instead of zero, so this actually matches up with the printed list index of 97022. It looks like our binary search script is working correctly.

Let's try our linear search and binary search scripts out with the time command and see how they compare. I've commented out the lines that print the indexes of matches in the two scripts, that way they'll still call their respective search functions for the 100 names we're searching for, but they won't actually print the indexes out, so we won't have a bunch of output obscuring the results of the time command. First, let's try the linear search script: time python linear_search.py names, and we can just use the unsorted list of names for linear search. Remember we want to ignore the real result and add the user and sys results together. It looks like it took about .9 seconds for linear search to find the 100 names in the list of one hundred thousand. Now let's try timing the binary search script: time python binarysearch.py names, and for this one we need to use the sorted list of names. Looks like that took around a quarter second, so less than half as long. Bear in mind that part of this time is spent loading the file of names into a list. The difference between linear search and binary search will be even more pronounced as you search through bigger lists or search for more items.

Let's wrap up the course by looking at the Big O runtimes for linear search and binary search. These are going to be much simpler to calculate than the sorting algorithms were. For linear search, you need to do one comparison to the target value for each item in the list. Again, theoretically we could find the target value before searching the whole list, but Big O notation is only concerned with the worst case, where we have to search the entire list. So for a list of eight items, that means eight operations. The Big O runtime for linear search is O(n), where n is the number of items we're searching through. This is also known as linear time because when the number of items and number of operations are compared on a graph, the result is a straight line. Linear search looks pretty good until you compare it to binary search. For binary search, the number of items you have to search through, and therefore the number of operations, is cut in half with each comparison. Remember the number of times you can divide n by two until you reach one is expressed as log n, so the runtime of binary search in Big O notation is O(log n). Even for very large values of n—that is, very large lists you have to search through—the number of operations needed to search is very small. Binary search is a very fast, efficient algorithm. That's our tour of sorting and searching algorithms. Be sure to check the teacher's notes for opportunities to learn more. Thanks for watching.