eastl::MergeSorter< RandomAccessIterator, T, StrictWeakOrdering, difference_type, InsertionSortLimit > Class Template Reference

#include <sort.h>

Static Public Member Functions
static void	sort (RandomAccessIterator first, RandomAccessIterator last, T *pBuffer, StrictWeakOrdering compare)

Detailed Description

template<typename RandomAccessIterator, typename T, typename StrictWeakOrdering, typename difference_type, int InsertionSortLimit>
class eastl::MergeSorter< RandomAccessIterator, T, StrictWeakOrdering, difference_type, InsertionSortLimit >

merge_sort_buffer

Implements the MergeSort algorithm with a user-supplied buffer. The input buffer must be able to hold a number of items equal to 'last - first'. Note that merge_sort_buffer requires a random access iterator, which usually means an array (eg. vector, deque).

The algorithm used for merge sort is not the standard merge sort. It has been modified to improve performance for data that is already partially sorted. In fact, if data is completely sorted, then performance is O(n), but even data with partially sorted regions can benefit from the modifications.

'InsertionSortLimit' specifies a size limit for which the algorithm will use insertion sort. Due to the overhead of merge sort, it is often faster to use insertion sort once the size of a region is fairly small. However, insertion sort is not as efficient (in terms of assignments orcomparisons) so choosing a value that is too large will reduce performance. Generally a value of 16 to 32 is reasonable, but the best choose will depend on the data being sorted.

---

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

• third_party/EASTL/include/EASTL/sort.h