Hello, and welcome to the sorting problem lesson. As usual, we start with a problem I'll review. So sorting is a fundamental computational problem. Your input in this problem consists of a sequence of elements, and your goal is to output this element in, for example, non-decreasing order. The formal statement of this problem is as follows. You are given a sequence of finite elements. We will usually denote the sequence by A throughout this lesson. And your goal is to output these same elements in non-decreasing order. Once again, sorting is an important computational task used in many efficient algorithms. For some algorithms, it is just as important to process given elements in non-decreasing order, going from smaller ones to larger ones. In some other algorithms, just by sorting your input data, you gain a possibility to perform your queries much more efficiently. A canonical example of such situation is a search problem. In this problem, we are given a sequence of finite elements. And your goal is to check whether a particular element is present in your sequence. A simple way to solve this problem, is of course, just to scan your input sequence from left to right and to check, whether your element is present in this sequence. This gives you a linear kind algorithm. And you know already that if you input data, if you input sequences you sorted, then you can do this much more faster. Basically, in time, in logarithmic time, in the size of your input sequence. So ou first compare your element to the middle element. If it is just few element, then you are done, if it is not, you continue with the left half of your sequence or the right half of your sequence. So in logarithmic number of comparison, and the worst case, you will be able to say whether your element is present in this sequence or not. So, if you are given a sequence and you are expecting many such queries. You're expecting to be asked to check whether a given object is present or not. For me such objects, then it just makes sense to first sort your input data and only then perform all these queries. This will give you a much more efficient algorithm in general. All right. And this is only a small example. We will see many other situations, where sorting your data first helps to perform queries much more efficiently. So in the subsequent videos of this lesson, we will study many efficient sorting algorithms.