SHA_Sort::MergeInPlace< IT > Class Template Reference

#include <merge.hxx>

Public Member Functions
void	operator() (IT begin, IT middle, IT end)

Detailed Description

template<typename IT>
class SHA_Sort::MergeInPlace< IT >

MergeInplace - Inplace merging of two ordered sequences of a collection Proceed a in place merge of two sequences of elements contained in [begin, middle[ and [middle, end[.

Warning

Both sequence [bengin, middle[ and [middle, end[ need to be ordered.

Remarks

use MergeWithBuffer to proceed the merge using a buffer: Takes higher memory consumption and lower computation consumption.

Complexity

O(N * M)

Template Parameters

IT

type.

Parameters

begin,middle,end

iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Returns

void.

Definition at line 46 of file merge.hxx.

Member Function Documentation

template<typename IT>

void SHA_Sort::MergeInPlace< IT >::operator() ( IT  begin, IT  middle, IT  end  )

inline

Definition at line 49 of file merge.hxx.

    {
      if (std::distance(begin, middle) < 1 || std::distance(middle, end) < 1)
        return;

      // Use first half as receiver
      for(; begin < middle; ++begin)
      {
        if (*middle >= *begin)
          continue;

        typename std::iterator_traits<IT>::value_type value;
        std::swap(value, *begin);    // keep the higher value
        std::swap(*begin, *middle);  // Place it at the beginning of the second list

        // Displace the higher value in the right place of the second list by swapping
        auto it = middle;
        for (; it != end - 1; ++it)
        {
          if (*(it + 1) >= value)
            break;

          std::swap(*it, *(it + 1));
        }

        // Restore the value at his right place
        std::swap(*it, value);
      }
    }

---

The documentation for this class was generated from the following file:

• merge.hxx