Intermediate Sorting Algorithms

This is the second article, in a series of 3, on which we will talk about Sorting Algorithms with tons of charts. In this one, we will see intermediate sorting algorithms with better time complexity. We will also have a playground at the end of the article, with async JavaScript code running with a remote API, similar to the one you saw in the first article (but better).

The JavaScript code runs on a Cloudflare Worker, called from the page. The graphics data were generated with a code written in C, compiled with GCC version $5.1.0$ which can be downloaded in this zip file containing the CSV data used as input.

Introduction

In the first article, we analyzed some basic sorting algorithms: Bubble Sort, Insertion Sort, and Shell Sort. In this one, we will analyze some better options with a $\Theta(n\log(n))$ time complexity, which are named QuickSort and MergeSort. We will also have some fun with a $\Theta(n)$ algorithm called RadixSort, which works only for numbers (it is pretty good, though). We will also have some special data structure demonstration to do something like a “merge” between files, containing ordered data. It will take all the data on the $n$ files, and make it ordered in a brand new file. We will make it following three different strategies: Quick Sort (same as in the first part), Merge Arrays (similar to the MergeSort seen before) and using Selection Trees (which uses a kind of HeapSort).

Part 1: sorting arrays

Talking about the first part of the article, in the folder with all the data, you can find sorting tests with different quantities of files, which can be read as <sortingAlgorithm><quantityOfFiles>.csv. The data below will refer to the data when tested against 200 files because it will make a better average time/recursion calls taken to go through the algorithm, as well as a better time/recursion calls standard deviation.

Quick Sort

QuickSort is probably the most known and used sorting algorithm. It is used (with some variations) in most of the built-in sort algorithms of programming languages. It has a worst case time complexity of $\Theta(n^2)$, but it occurs so rarely (if implemented the right way), that its average case time complexity is the long-sought $\Theta(n\log(n))$.

It was used arrays varying from $2^1$ until $2^{19}$ (random generated numbers) to generate the data below, as we couldn’t use larger arrays cause of recursion depth limit. The left y-axis shows the time and the right one shows the recursive calls. As a reminder, the sorted charts may be a bit wrong in the time dataset, as explained in the previous article (TLDR: OS interruptions can cause this).

The code used for it can be seen below, followed by the chart showing the data (in the test with the 200 files, as said before).

int partition(int* C, int low, int high)
{
    int random = (rand() % (high - low)) + low, p=high, i=low-1, j, temp;

    // Random pivot to make it better sorting already sorted stuff
    temp = C[random];
    C[random] = C[high];
    C[high] = temp;

    for(j=low; j<=high-1; j++)
    {
        if(C[j]<=C[p])
        {
            i++;
            temp=C[i];
            C[i]=C[j];
            C[j]=temp;
        }
    }
    i++;
    temp = C[i];
    C[i] = C[p];
    C[p] = temp;

    return i;
}

void quickSort(int* C, long long int low, long long int high)
{
    int p;

    if (high>low)
    {
        p = partition(C, low, high);
        quickSort(C, low, p-1);
        quickSort(C, p+1, high);
    }

    return;
}

We also have more data about it, which you can find in the CSV files, linked above. Quicksort has a standard deviation of 0.01s when talking about the time taken to make it, as well as a standard deviation of roughly 300 recursive calls, which is not that much, actually. If we compare Quick Sort, with the algorithms seen in the other article, we can see a HUGE difference (you can see that difference in the Playground below).

Merge Sort

Let’s move on to another sorting algorithm which almost everybody knows. It also has an average time complexity of $\Theta(n\log(n))$, having it as its worst-case time complexity as well.

The code used for it can be seen below, followed by the charts showing the data.

void merge(int *C, int* Aux, int start, int mid, int end)
{
    int k, i = start, j = mid+1;

    for(k=start; k<=end; k++)
        Aux[k] = C[k];

    for(k=start; k<=end; k++)
    {
        if (i>mid)
            C[k] = Aux[j++];
        else if (j>end)
            C[k] = Aux[i++];
        else if (Aux[i] <= Aux[j])
            C[k] = Aux[i++];
        else
            C[k] = Aux[j++];
    }

    return;
}

void mergeSort(int *C, int* Aux, int start, int end)
{
    int mid;

    if(end>start)
    {
        // Midpoint between the start and the end
        mid = (start+end) / 2;

        mergeSort(C, Aux, start, mid);
        mergeSort(C, Aux, mid+1, end);
        merge(C, Aux, start, mid, end);
    }

    return;
}

What is really nice about MergeSort is that it makes the exact same amount of recursive calls every time, doesn’t matter how the array is ordered, so we have 0 as its standard deviation for recursive calls, and an average standard deviation of 0.01s, similar to QuickSort. That happens because it ALWAYS splits the array exactly in the middle, which didn’t happen with QuickSort, which could make the recursion tree pretty unbalanced. Below you will be able to see that Merge Sort is actually a bit slower than QuickSort, and that’s why we don’t see it implemented as the standard sorting algorithm in a lot of programming languages. A factor that causes it to take more time, is that it has a lot more recursive calls comparing to QuickSort (1048575 vs 702256, when tested against 524288 numbers). Something really nice is that we can see how MergeSort creates a perfect tree looking to the number of recursive calls. It will always represent $n * 2 - 1$, with $n =$ quantity of numbers to be sorted.

Radix Sort

RadixSort should be, in theory, an incredibly fast algorithm to sort numbers. It has a $\Theta(n)$ time complexity and doesn’t make a single comparison to sort the numbers, although it uses some auxiliary memory.

Its basic idea is that it uses $10$ stacks, to put each number in a different one according to a specific digit of it (that’s why it only works for specific kinds of data, like integers and strings). If you order the numbers going from the least significant digit to the most significant one, using a stack to maintain its stability, you have a really fast algorithm, which can be seen below, as well as a chart to see some information about it:

int digitAt(int value, int position){
  int r;

  r = value % pow(10, position+1);
  r = r / pow(10, position);

  return r;
}

int* radixSort(int* A, int size)
{
    int d, i, digit;
    int *C = (int*) malloc(10*sizeof(int)),
        *B = (int*) malloc(size*sizeof(int));

    for(d=0; d<MAX_DIGITS; d++){

      // Reset the counting array
      for(i=0; i<10; i++)
        C[i] = 0;

      // Count how many numbers have each digit
      for(i=0; i<size; i++)
        C[digitAt(A[i], d)]++;

      // Prefix sums, so equal digits keep their order (stability)
      for(i=1; i<10; i++)
        C[i] += C[i-1];

      // Place each number in its sorted position
      for(i=size-1; i>=0; i--){
        digit = digitAt(A[i], d);
        B[C[digit] - 1] = A[i];
        C[digit]--;
      }

      // Copy back from the auxiliary array
      for(i=0; i<size; i++)
        A[i] = B[i];
    }

    free(C);

    return B;
}

It’s kinda interesting because RadixSort doesn’t look THAT fast if we compare with the others which we tried before (we have a chart below). It is really nice, because it actually has no recursion, being purely iterative, and doesn’t make a single comparison, just a huge numerical manipulation, which is really impressive. That algorithm is called LSD Radix Sort (LSD stands for least-significant-digit) because we order according to the least significant digit before. If we would sort it with an MSD RadixSort, we would need to change our code, and add some comparisons, because just ordering from the most to the least significant digit, wouldn’t sort the numbers accordingly. RadixSort has a 0.02 seconds standard deviation, which is pretty low, similar to the others. The standard deviation of recursive calls is 0, as it doesn’t make any recursion or comparison at all.

Comparing the three

Here we will put all the last 3 algorithms together, to see a comparison between the time they take to sort the different arrays sizes. It will also be used the dataset referring to the 200 files input, as it has a better probabilistic chance of representing the real average time for their execution.

As said before, it is weird that RadixSort is slower than the others, which I assume is something related to the function that takes the digit from the number, as it has some potentiation and modulo arithmetic, which take a lot of computation. Something crazy we can see when testing with the Playground below, is that Javascript is some orders of magnitude slower than C to make a QuickSort sorting.

Part 2: merging sorted files

This second part was divided trying three different “data structures”.

We have $n$ different files with numbered data inside of it. The point is that each file has its data ordered, and our mission is to create a huge new file containing all the data in those files, ordered as well.

In this part, we have a problem. As our final array can be HUGE according to the size of the input arrays, and the number of input files which will be merged, some types of data structures only have data up to $2^{14}$ for some quantity of files, while the most of it will have data up to $2^{19}$

The first one, which will be referred as “Files Quick Sort”, is a kind of application of Quick Sort Algorithm. It is the one with problems with huge arrays because it will reach maximum recursion depth really fast. It will be the slower of the three structures, as the fact of the data inside of the files being already ordered doesn’t make any difference, because it will try to sort it anyway.

The second one will be called “Merge Arrays”, and is somewhat similar to a Merge Sort algorithm, but taking into consideration that we already separated and merge most of the arrays, making the algorithm just the merge part of the MergeSort full algorithm, or, if you prefer, just the part where you are “coming back” from the recursion.

The third implementation, called “Selection Tree”, uses a Minimum Heap to sort all the data in the files. A Heap is a special type of data tree stored in the format of an array. We will have the top of our files in the “leaves” of the heap, and the smallest number in all the files in the root of the tree. Each step, we remove the smallest one, inserting it in the final sorted array, and moving the smallest number back to the root of the heap.

All the implementations can be seen in the codes below (QuickSort will be omitted, as it has already been shown before), as well as a chart comparing the three different structures.

void mergeSortedArrays(int** input, int* output, int p, int N)
{
    int i, k, smallest, index=-1;
    for(i=0; i<N; i++){
      smallest = topFromArray(input, 0);
      index = 0;
      for(k=1; k<p; k++){
        if (topFromArray(input, k) < smallest){
          smallest = topFromArray(input, k);
          index = k;
        }
      }
      output[i] = popFromArray(input, index);
    }

    return;
}

void heapify(int* heap, int** input, int p, int i){
  int left, right, smallest;

  while(i < p-1){
    left = 2*i + 1;
    right = 2*i + 2;
    smallest = heap[left] <= heap[right] ? left : right;
    heap[i] = heap[smallest];
    i = smallest;
  }

  heap[i] = popFromArray(input, i-p+1);

  return;
}

int* buildHeap(int* heap, int** input, int p, int heapSize){

  // Heapify it, pulling stuff from the files
  for(int i=heapSize-1; i>=0; i--)
    heapify(heap, input, p, i);

  return heap;
}

int popFromSelectionTree(int* tree, int size, int** input, int p)
{
    int r = tree[0], i = 0, smallest;

    while(i < p-1){
      smallest = tree[2*i + 1] <= tree[2*i + 2] ? 2*i + 1 : 2*i + 2;
      tree[i] = tree[smallest];
      i = smallest;
    }

    tree[i] = popFromArray(input, i-p+1);

    return r;
}

void mergeWithSelectionTree(int** input, int* output, int p, int n)
{
    int size=2*p-1, i;
    int* tree = buildHeap((int*) malloc(size*sizeof(int)), input, p, size);

    for(i=0; i<n; i++)
      output[i] = popFromSelectionTree(tree, size, input, p);

    return;
}

It’s interesting, because QuickSort gets the prize for fastest, although I wasn’t expecting that, as the others are REALLY fast. The problem is that, as we go to bigger array sizes, Quick Sort just COMPLETELY crashes (in the chart above, it couldn’t sort 6.5 million numbers). I think this happens because, as we are testing with 200 files, our final array size will be kinda big, so the recursion will be HUGE to handle all this sorting. Maybe I implemented something wrong, but I don’t think that is the case, because it starts to crash just when testing against TONS of files, with huge array sizes in it. Another interesting thing is that the merging technique has almost the same average time taken as the heap sort/selection tree one, and god, they are REALLY fast, because as you can see they take roughly 0.62s to sort incredible 104 MILLION numbers (okay, the numbers are partially ordered and the algorithms abuse of this, but it is something really awesome anyway).

Playground

These algorithms were also “translated” to JavaScript, which you can play with in the table below. The sorting runs on a Cloudflare Worker rather than in your browser. The Time column is the round trip measured from the page, network latency included, because the Worker runtime freezes its clock during synchronous execution and so cannot time itself - expect a floor of about a tenth of a second regardless of the array. Arrays are capped at 25,000 elements to stay inside the Worker CPU budget. These times are much slower than the C ones used for the graphics above, but if you run the same code yourself you will see that asynchronous JavaScript makes some sorting algorithms REALLY fast (you can see the explanation in the latter article). Hope you enjoyed, and see you next time!

This article was first written as a report for the Data Search & Classification 📊 Subject at the CS Bsc. course at UFRGS, and adapted to this blog post. You can find the original post with the API running on a Node.JS backend (some order of magnitudes faster than this one up here) on this repository tag on my Github.