<commit_before>---
layout: post
title: Cutting off quick-sort
excerpt: Quick-sort is fast in practice but is beaten by insertion sort on small datasets. From this observation, we can design an hybrid algorythm to reap the best of the both.
---
 
The quick-sort algorithm has been developed by <NAME> in 1960, with expected `O(n log n)` comparisons and `O(log n)` memory space to sort `n` items. The quick-sort outperform the others in practice, but there is no guarantee. When it spins off the road the complexity becomes quadratic. It is a classic recipe with many variants. Indeed writing a robust implementation that avoids quadratic response time reveals challenging, but that's another story. Here is a naive quick-sort implementation.

{% highlight java %}
    /**
     * @param lo index of the first sorted element
     * @param hi index of the last sorted element
     */
    static void quickSort(int[] array, int lo, int hi) {
        if (hi <= lo) return;
        int pivot = array[hi], firstBig = lo, tmp;
        for (int i = lo; i < hi; i++) {            
            if ((tmp = array[i]) < pivot) {
                array[i] = array[firstBig];
                array[firstBig++] = tmp;
            }
        }
        array[hi] = array[firstBig];
        array[firstBig] = pivot;
        sort(array, lo, firstBig - 1);
        sort(array, firstBig + 1, hi);
    }
{% endhighlight %}

The insertion sort is a quadratic sorting algorithms. Despite of its poor asymptotic performance, the insertion sort reveals to have a lot of interesting properties.
 - It is a simple iterative algorithm. Theses few lines of code outperform others algorithms on small datasets.
 - It is efficient on almost sorted arrays.

{% highlight java %}<commit_msg>Fix headline<commit_after>---
layout: post
title: Cutting off quick-sort
excerpt: Quick-sort is fast in practice but is beaten by insertion sort on small datasets. From this observation, we can design an hybrid algorythm to reap the best of both.
---
 
The quick-sort algorithm has been developed by <NAME> in 1960, with expected `O(n log n)` comparisons and `O(log n)` memory space to sort `n` items. The quick-sort outperform the others in practice, but there is no guarantee. When it spins off the road the complexity becomes quadratic. It is a classic recipe with many variants. Indeed writing a robust implementation that avoids quadratic response time reveals challenging, but that's another story. Here is a naive quick-sort implementation.

{% highlight java %}
    /**
     * @param lo index of the first sorted element
     * @param hi index of the last sorted element
     */
    static void quickSort(int[] array, int lo, int hi) {
        if (hi <= lo) return;
        int pivot = array[hi], firstBig = lo, tmp;
        for (int i = lo; i < hi; i++) {            
            if ((tmp = array[i]) < pivot) {
                array[i] = array[firstBig];
                array[firstBig++] = tmp;
            }
        }
        array[hi] = array[firstBig];
        array[firstBig] = pivot;
        sort(array, lo, firstBig - 1);
        sort(array, firstBig + 1, hi);
    }
{% endhighlight %}

The insertion sort is a quadratic sorting algorithms. Despite of its poor asymptotic performance, the insertion sort reveals to have a lot of interesting properties.
 - It is a simple iterative algorithm. Theses few lines of code outperform others algorithms on small datasets.
 - It is efficient on almost sorted arrays.

{% highlight java %}
{'fraction_non_alphanumeric': 0.0828808230923121, 'fraction_numerical': 0.003429551300371535, 'mean_word_length': 2.833515881708653, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4727979', 'n_tokens_mistral': 952, 'n_tokens_neox': 880, 'n_words': 460}