<commit_before>/*
    Copyright (c) 2013-2014 <NAME>
    Modified in 2015 by Morwenn for inclusion into cpp-sort

    This software is provided 'as-is', without any express or implied warranty. In no event will the
    authors be held liable for any damages arising from the use of this software.

    Permission is granted to anyone to use this software for any purpose, including commercial
    applications, and to alter it and redistribute it freely, subject to the following restrictions:

    1. The origin of this software must not be misrepresented; you must not claim that you wrote the
       original software.

    2. If you use this software in a product, an acknowledgment in the product documentation would be
       appreciated but is not required.

    3. Altered source versions must be plainly marked as such, and must not be misrepresented as
       being the original software.
*/

#ifndef CPPSORT_DETAIL_INPLACE_MERGE_SORT_H_
#define CPPSORT_DETAIL_INPLACE_MERGE_SORT_H_

#include <cstddef>
#include <iterator>
#include <utility>

namespace cppsort
{
namespace detail
{
    /// in-place Merge Sort, allow user-defined less-than operator
    template <typename iterator, typename LessThan>
    void inplace_merge_sort(iterator first, iterator last, LessThan lessThan, std::size_t size = 0)
    {
      // determine size if not known yet
      if (size == 0 && first != last)
        size = std::distance(first, last);
      // by the way, the size parameter can be omitted but
      // then we are required to compute it each time which can be expensive
      // for non-random access iterators

      // one element is always sorted
      if (size <= 1)
        return;

      // divide into two partitions
      std::size_t firstHalf  = size / 2;
      std::size_t secondHalf = size - firstHalf;
      iterator mid = first;
      std::advance(mid, firstHalf);

      // recursively sort them
      inplace_merge_sort(first, mid,  lessThan, firstHalf);
      inplace_merge_sort(mid,   last, lessThan, secondHalf);

      // merge partitions (left starts at "first", right starts and "mid")
      // move iterators towards the end until they meet<commit_msg>No need to compute the size. We know it.<commit_after>/*
    Copyright (c) 2013-2014 <NAME>
    Modified in 2015 by Morwenn for inclusion into cpp-sort

    This software is provided 'as-is', without any express or implied warranty. In no event will the
    authors be held liable for any damages arising from the use of this software.

    Permission is granted to anyone to use this software for any purpose, including commercial
    applications, and to alter it and redistribute it freely, subject to the following restrictions:

    1. The origin of this software must not be misrepresented; you must not claim that you wrote the
       original software.

    2. If you use this software in a product, an acknowledgment in the product documentation would be
       appreciated but is not required.

    3. Altered source versions must be plainly marked as such, and must not be misrepresented as
       being the original software.
*/

#ifndef CPPSORT_DETAIL_INPLACE_MERGE_SORT_H_
#define CPPSORT_DETAIL_INPLACE_MERGE_SORT_H_

#include <cstddef>
#include <iterator>
#include <utility>

namespace cppsort
{
namespace detail
{
    /// in-place Merge Sort, allow user-defined less-than operator
    template <typename iterator, typename LessThan>
    void inplace_merge_sort(iterator first, iterator last, LessThan lessThan, std::size_t size)
    {
      // one element is always sorted
      if (size <= 1)
        return;

      // divide into two partitions
      std::size_t firstHalf  = size / 2;
      std::size_t secondHalf = size - firstHalf;
      iterator mid = first;
      std::advance(mid, firstHalf);

      // recursively sort them
      inplace_merge_sort(first, mid,  lessThan, firstHalf);
      inplace_merge_sort(mid,   last, lessThan, secondHalf);

      // merge partitions (left starts at "first", right starts and "mid")
      // move iterators towards the end until they meet
{'fraction_non_alphanumeric': 0.06321979906885568, 'fraction_numerical': 0.008821367311933349, 'mean_word_length': 3.1399594320486814, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 13, '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': '4032577', 'n_tokens_mistral': 1167, 'n_tokens_neox': 1078, 'n_words': 497}