Theory on logarithmic sorting

Logarithmic sorts are sorting algorithms that have a complexity of $O(N\log N)$ and use only element comparisons. They allow you to sort an array with a length of 100 000 — 1000 000 in one second. These are the ones you should use in most tasks that require sorting.

There are a huge number of different logarithmic sorts, but three are really widely used:

• Quick sort, aka Hoare sort, Hoare quick sort, or simply qsort;
• Merge sort;
• Heap sort.

In this text I will describe merge sorting and quick sorting. Sorting by the heap will be in the topic about the heap at level 5A.

QuickSort

Idea

The idea of sorting is very simple. Suppose we need to sort some piece of the array. Let's take an arbitrary element in this piece of the array, let this element be equal to $x$. Rearrange the remaining elements of this piece so that all the elements of $\leq x$ go first, and then all the elements of $\geq x$. (There are many variations on where to allow non-strict inequality here, and where to require strict inequality.) This can be done in one pass through the array. After that, it remains to sort both received chunks separately, which we will do with two recursive runs.

How exactly to do the required partitioning? Usually they do this: they run two pointers from two ends of the considered piece of the array. First, they go with one pointer from left to right, starting from the left end, skipping the numbers that are $<x$ — they are quite in their places. When there is an element that is $\geq x$, the pointer stops. After that, they go with the second pointer from right to left, starting from the right end, skipping the elements that are $>x$ — they are also quite in their places. When the element $\leq x$ is found, it is swapped with the element that was found by the first pointer. After that, both of these elements are also obtained in their places, and the pointers go further. And so on until the pointers are reversed.

Implementation

The classic implementation is as follows (I took it from here):

// сортируем массив A на участке от left до right
procedure quicksort(left, right : integer);
var i, j :integer;
    tmp, x :integer;
begin
  i:=left;
  j:=right;
  x := A[(left + right) div 2]; // choosing x, see the discussion of this line below
  repeat
    while x>A[i] do inc(i); // we skip those elements that are in their places
    while x<A[j] do dec(j); // we skip those elements that are in their places
    if i<=j then begin
      // found two elements that are out of place
      // --- swap them
      tmp:=A[i];
      A[i]:=A[j];
      A[j]:=tmp;
      dec(j);
      inc(i);
    end;
  until i>j;
  // if there is more than one element in the left part, then sort it
  if left<j then quicksort(left,j);
  // similarly for the right part
  if i<right then quicksort(i,right);
end;

Both the idea and the implementation look simple, but in fact there are a lot of pitfalls here. Try to understand this code now, understand it, and then close this page and write a program — almost certainly the resulting program will not work or will not always work. Moreover, if you try to understand what is wrong with your program and compare it with the code above, you will not understand why the differences are so important.

Therefore, in my opinion, the only way to learn how to write quicksort, at least at your current level, is to find an exactly working implementation and learn it by heart (by the way, I'm not 100% sure that the code above really works). Maybe when you get really cool, you'll be able to understand all the pitfalls of quicksort, but it's unlikely now. If you have not learned it by heart, then I strongly do not recommend you to write it in real problems. It's better to master merge sorting, which I write about below.

Complexity

What is the complexity of quicksort? If you think a little with your head, it is clear that in the worst case its complexity is $O(N^2)$. Indeed, if each time we are unlucky and each time we choose the smallest element of the current piece as $x$, then each time the length of the sorted piece will decrease only by one, and the depth of recursion will be $N$, and at each level of recursion it will be approximately $N$ actions — total $O(N^2)$

But at the same time, quick sort is the rarest example of an algorithm whose complexity is on average better than in the worst case. Namely, let's first look at the ideal case. Ideally, at each iteration, the array will be divided exactly in half, and the recursion depth will be only $\log N$. Total complexity $O(N\log N)$. It is stated that on average (i.e. if the input data is random) the complexity will also be $O(N\log N)$.

However, there is a setup: the input data is never random. If we choose $x$ in a very specific way, for example, as in the example above — always the middle element of the array, then an evil user (or an evil jury) will always be able to pick up such an example so that our sorting works very poorly, i.e. for $O(N^2)$. (And it would be even worse to always take the very first or the very last element — then not only an evil user could pick up a special test, but also simply if the input data is already sorted, and this happens not for evil users, then sorting will work for $O(N^2) $).

You can fight against this by selecting the element each time in a random way, i.e. using random. Just don't forget to do randomize to predict which element you will choose, it was really difficult.

$k$-th ordinal statistics

In addition to sorting itself, quicksort's ideas have another use. Let us be given an unsorted array and a number $k$. Let's ask ourselves: what number will be in the $k$-th place if the array is sorted? This number is called the $k$th ordinal statistic (i.e., for example, the 137th ordinal statistic is the number that will be in 137th place).

To find the $k$th ordinal statistics, you can, of course, sort the array - the complexity of the solution will be $O(N\log N)$. But you can do it easier. Let's split the array into two parts, as in quicksort. Quicksort then runs recursively for both received parts, but we don't need this — we know how many elements are in which part and therefore we know which part the $k$th element falls into. Therefore, it is enough for us to make only one recursive run. As a result, we can prove that the average complexity is $O(N)$.

Merge sorting

Merging two arrays

First, let's look at a simpler problem. Suppose we have two already sorted arrays, and we need to combine them into one sorted. For example, if there are two arrays

a1 = 1 6 7 9
a2 = 2 3 7 10

then you should get an array

res = 1 2 3 6 7 7 9 10

How to do it? Obviously, either the first element of the first array or the first element of the second array should be in the first place, since all other numbers are greater than them. Select the element that is smaller, put it in the output array and delete it from the corresponding source array.:

a1 =   6 7 9
a2 = 2 3 7 10
res = 1

After that, let's compare the two numbers that are now at the beginning of the original arrays (in this case, 2 and 6). Again, select the smallest of them and move it to the final array, etc. As a result, in one pass through each of the source arrays, we will get a sorted array.

It is written quite easily. Of course, we will not actually delete elements from the source arrays, but we will simply create pointers (indexes) i1 and i2, which will show which elements in both source arrays are current. The following code is obtained:

i1:=1;
i2:=1;
for i:=1 to n1+n2 do // n1, n2 -- the number of elements in the source arrays
    if (i1<=n1) and ( (i2>n2) or (a1[i1]<a2[i2]) ) then begin
        res[i]:=a1[i1];
        inc(i1);
    end else begin
        res[i]:=a2[i2];
        inc(i2);
    end;

Everything is simple here, except for the condition in if. It would seem that there should be a banal if a1[i1]<a2[i2] — but no, the fact is that at some point one of the source arrays will end, and it will not be so easy to compare. Therefore, there is a slightly more complex condition. Namely, when should I take an element from the first array? Well, first of all, of course, only if the first array has not ended yet: i1<=n1. Secondly, if the first array has not ended, then we need to look at the second array. Either the second array has ended (and then we take it from the first array for sure), or it has not ended, and then we must honestly compare a1[i1] and a2[i2]. Therefore, there is nothing particularly complicated in the if condition, everything is quite clear if you remember that arrays can end.

Actually merge sorting

Now the original problem of sorting an unsorted array can be solved like this. Let's split the source array into two halves. Recursively sort each one by running the same algorithm. After that, we have two sorted halves — we will merge them as described above.

This is written quite easily:

var a:array[1..100000] of integer; // the array that we are sorting
    aa:array[1..100000] of integer; // auxiliary array

procedure sort(l,r:integer); // sorting a piece of the array from l to r inclusive
var i,i1,i2,o:integer;
begin
if l>=r then exit; // if the piece is short, then there is nothing to sort
                   // this is also a condition for exiting recursion
o:=(l+r) div 2;
// split into two halves: (l..o) and (o+1..r)
// let's sort them
sort(l,o);
sort(o+1,r);
// merge into the temporary array
i1:=l;
i2:=o+1;
for i:=l to r do 
    if (i1<=o)and((i2>r)or(a[i1]<a[i2])) then begin
        aa[i]:=a[i1];
        inc(i1);
    end else begin
        aa[i]:=a[i2];
        inc(i2);
    end;
// move from the temporary array the the main array
for i:=l to r do
    a[i]:=aa[i];
end;

In principle, everything is clear here. You just need to carefully write the condition in the if, without getting confused, where is the strict and where is the non-strict inequality, but since you understand the argument ("what if the array has ended?"), then everything is simple. Also, don't get confused where o is and where o+1 is, but it's also simple, because o is the last element of the first half of the array.

Of course, merge sorting can be written somewhat faster, but it is usually not required.

Complexity

With the complexity of merge sorting, everything is easier. Each sort procedure works in linear time from the length of the sorted piece, without taking into account recursive runs. At the top level of recursion, we get one run from the entire array — time $O(N)$. At the next level of recursion, we get two runs on two halves of the array, but in total these halves make up the whole array, so in total the time of these two runs is also $O(N)$. At the third level, we have four quarters, which in total also give $O(N)$. The levels of all, as it is easy to see, are $\log N$, in total we get the complexity of $O(N \log N)$.

Counting the number of inversions

Merge sorting has the following application. Let there be an unsorted array. Inversion (or disorder) in this array, we call any two elements that are in the wrong order relative to each other. For example, in the array 4 3 5 2 there are four inversions: 4 goes before 3; 4 goes before 2; 3 goes before 2; 5 goes before 2.

How can I count the number of inversions? You can just check all pairs, but it will be $O(N^2)$. Or you can use some sort of sorting. Namely, when we rearrange an element in some sort, we will see how many other elements that are larger than it, but which went earlier in the original order, it "overtook". In many cases, it turns out exactly the number of inversions that "disappeared" in our array after this permutation. In the end, there will be no inversions in the resulting sorted array, so that's how many inversions disappeared in total, so many of them were originally.

The simplest example is bubble sorting. Every time she swaps two elements, one inversion disappears. Therefore, the number of exchanges in bubble sorting is just the number of inversions. Similarly, in sorting by inserts: when we take another element and move it a few positions to the left — that's how many positions, so many inversions we have removed. But in sorting by choosing the maximum, it will not be so easy to calculate inversions, because when we rearrange an element there, we do not know — among those elements whom it "overtook", how many were more than it, and how many were less. (Of course, this can be calculated, but then it's easier to make an honest calculation of inversions by checking all pairs.)

For the same reasons, quicksort cannot be adapted to count inversions: when we swap two elements, we do not know how many inversions disappear, because we do not know which elements are in the middle.

But merge sorting can be adapted. Maybe it's not so obvious, but when we take an element from the first half (a[i1]), then we don't remove any inversion, and when we take an element from the second half (a[i2]), then we remove the o-i1+1 inversion: it overtakes the elements of the first half that have not yet been taken, and at the same time all these elements are larger than it. Therefore, we get the following code:

procedure sort(l,r:integer);
var i,i1,i2,o:integer;
begin
if l>=r then exit;
o:=(l+r) div 2;
sort(l,o);
sort(o+1,r);
i1:=l;
i2:=o+1;
for i:=l to r do 
    if (i1<=o)and((i2>r)or(a[i1]<=a[i2])) then begin
        aa[i]:=a[i1];
        inc(i1);
    end else begin
        inversions:=inversions+o-i1+1; 
        aa[i]:=a[i2];
        inc(i2);
    end;
for i:=l to r do
    a[i]:=aa[i];
end;

The answer is in the variable inversions. Note that there is another difference in this code from the sorting code given above, and understand why this is so.