<commit_before>#ifndef SORTING_INCLUDE_EFFICIENTSORTS_QUICK_INL_H_
#define SORTING_INCLUDE_EFFICIENTSORTS_QUICK_INL_H_

namespace sorting {
namespace efficient {

template <class T>
void Quicksort(T * const array, const int N)
{
    // Return if array size is 1 or less
    if (N <= 1)
    {
        return;
    }
    else if (N == 2)
    {
        // If two elements in the array, sort them manually and return
        if (array[0] > array[1])
        {
            std::swap(array[0], array[1]);
        }
        return;
    }

    // Use the last element in the array as the pivot
    int pivot = N-1;
    // Indices of left and right elements to swap:
    //      array[i0] < array[pivot] and array[i1] > array[pivot]
    int i0 = 0;
    int i1 = pivot-1;
    // Loop until break statement reached
    while (true)
    {
        // Store previous values so we know where to start looking for the next
        // possible elements to swap
        const int prev_i0 = i0;
        const int prev_i1 = i1;
        // Reset indices. Later, we detect if these values were changed.
        i0 = -1;
        i1 = -1;

        // Find the first element that is larger than the pivot
        for (int i = prev_i0 ; i < pivot ; i++)
        {
            if (array[i] > array[pivot])
            {
                i0 = i;
                break;
            }<commit_msg>Optimization: use media of first, middle and last element as the pivot in quicksort.<commit_after>#ifndef SORTING_INCLUDE_EFFICIENTSORTS_QUICK_INL_H_
#define SORTING_INCLUDE_EFFICIENTSORTS_QUICK_INL_H_

#include "simplesorts-insertion-inl.h"

namespace sorting {
namespace efficient {

template <class T>
void Quicksort(T * const array, const int N)
{
    // Return if array size is 1 or less
    if (N <= 1)
    {
        return;
    }
    else if (N == 2)
    {
        // If two elements in the array, sort them manually and return
        if (array[0] > array[1])
        {
            std::swap(array[0], array[1]);
        }
        return;
    }

    // Optimization: Choose median of first, middle and last element as the pivot
    int indices_tmp[3] = {0, (N/2)-1, N-1};
    sorting::simple::InsertionSort(indices_tmp, 3);
    const int pivot = N-1;
    // Place pivot element at its location (end of array)
    std::swap(array[indices_tmp[1]], array[pivot]);

    // Indices of left and right elements to swap:
    //      array[i0] < array[pivot] and array[i1] > array[pivot]
    int i0 = 0;
    int i1 = pivot-1;
    // Loop until break statement reached
    while (true)
    {
        // Store previous values so we know where to start looking for the next
        // possible elements to swap
        const int prev_i0 = i0;
        const int prev_i1 = i1;
        // Reset indices. Later, we detect if these values were changed.
        i0 = -1;
        i1 = -1;

        // Find the first element that is larger than the pivot
        for (int i = prev_i0 ; i < pivot ; i++)
        {
            if (array[i] > array[pivot])
            {
                i0 = i;
                break;
            }
{'fraction_non_alphanumeric': 0.09610389610389611, 'fraction_numerical': 0.017857142857142856, 'mean_word_length': 1.8902439024390243, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, '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': '5196943', 'n_tokens_mistral': 1004, 'n_tokens_neox': 968, 'n_words': 340}