text: ///////////////////////////////////////////////////////////////////////////////
  // Copyright (c) Electronic Arts Inc. All rights reserved.
  //////////////////////////////////////////////////////////////////////////////
  
  //////////////////////////////////////////////////////////////////////////////
  // This file implements sorting algorithms. Some of these are equivalent to 
  // std C++ sorting algorithms, while others don't have equivalents in the 
  // C++ standard. We implement the following sorting algorithms:
  //    is_sorted             -- 
  //    sort                  -- Unstable.    The implementation of this is mapped to quick_sort by default.
  //    quick_sort            -- Unstable.    This is actually an intro-sort (quick sort with switch to insertion sort).
  //    tim_sort              -- Stable.
  //    tim_sort_buffer       -- Stable.
  //    partial_sort          -- Unstable.
  //    insertion_sort        -- Stable. 
  //    shell_sort            -- Unstable.
  //    heap_sort             -- Unstable. 
  //    stable_sort           -- Stable.      The implementation of this is simply mapped to merge_sort.
  //    merge                 -- 
  //    merge_sort            -- Stable. 
  //    merge_sort_buffer     -- Stable. 
  //    nth_element           -- Unstable.
  //    radix_sort            -- Stable.      Important and useful sort for integral data, and faster than all others for this.
  //    comb_sort             -- Unstable.    Possibly the best combination of small code size but fast sort.
  //    bubble_sort           -- Stable.      Useful in practice for sorting tiny sets of data (<= 10 elements).
  //    selection_sort*       -- Unstable.
  //    shaker_sort*          -- Stable.
  //    bucket_sort*          -- Stable. 
  //
  // * Found in sort_extra.h.
  //
  // Additional sorting and related algorithms we may want to implement:
  //    partial_sort_copy     This would be like the std STL version.
  //    paritition            This would be like the std STL version. This is not categorized as a sort routine by the language standard.
  //    stable_partition      This would be like the std STL version.
  //    counting_sort         Maybe we don't want to implement this.
  //
  //////////////////////////////////////////////////////////////////////////////
  
  
  #ifndef EASTL_SORT_H
  #define EASTL_SORT_H
  
  
  #include <EASTL/internal/config.h>
  #include <EASTL/internal/move_help.h>
  #include <EASTL/iterator.h>
  #include <EASTL/memory.h>
  #include <EASTL/algorithm.h>
  #include <EASTL/functional.h>
  #include <EASTL/heap.h>
  #include <EASTL/allocator.h>
  #include <EASTL/memory.h>
  
  
  #if defined(EA_PRAGMA_ONCE_SUPPORTED)
  	#pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result.
  #endif
  
  
  // EASTL_PLATFORM_PREFERRED_ALIGNMENT
  //
  // Allows for slightly faster buffers in some cases.
  //
  #if !defined(EASTL_PLATFORM_PREFERRED_ALIGNMENT)
  	#if defined(EA_PROCESSOR_ARM)
  		#define EASTL_PLATFORM_PREFERRED_ALIGNMENT 8
  	#else
  		#define EASTL_PLATFORM_PREFERRED_ALIGNMENT 16
  	#endif
  #endif
  
  
  namespace eastl
  {
  
  	/// is_sorted
  	///
  	/// Returns true if the range [first, last) is sorted.
  	/// An empty range is considered to be sorted.
  	/// To test if a range is reverse-sorted, use 'greater' as the comparison 
  	/// instead of 'less'.
  	///
  	/// Example usage:
  	///    vector<int> intArray;
  	///    bool bIsSorted        = is_sorted(intArray.begin(), intArray.end());
  	///    bool bIsReverseSorted = is_sorted(intArray.begin(), intArray.end(), greater<int>());
  	///
  	template <typename ForwardIterator, typename StrictWeakOrdering>
  	bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare)
  	{
  		if(first != last)
  		{
  			ForwardIterator current = first;
  
  			for(++current; current != last; first = current, ++current)
  			{
  				if(compare(*current, *first))
  				{
  					EASTL_VALIDATE_COMPARE(!compare(*first, *current)); // Validate that the compare function is sane.
  					return false;
  				}
  			}
  		}
  		return true;
  	}
  
  	template <typename ForwardIterator>
  	inline bool is_sorted(ForwardIterator first, ForwardIterator last)
  	{
  		typedef eastl::less<typename eastl::iterator_traits<ForwardIterator>::value_type> Less;
  
  		return eastl::is_sorted<ForwardIterator, Less>(first, last, Less());
  	}
  
  
  
  	/// is_sorted_until
  	///
  	/// Returns an iterator to the first element in the range [first,last) which does not follow an ascending order.
  	/// The range between first and the iterator returned is sorted.
  	/// If the entire range is sorted, the function returns last.
  	/// The elements are compared using operator< for the first version, and comp for the second.
  	///
  	/// Example usage:
  	///     vector<int> intArray;
  	///     vector<int>::iterator unsorted_element = is_sorted_until(eastl::end(intArray), eastl::end(intArray));
  	///     vector<int>::iterator unsorted_element_with_user_compare = is_sorted_until(eastl::end(intArray), eastl::end(intArray), eastl::less<int>());
  	///
  	template<typename ForwardIterator>
  	ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last)
  	{
  		if(first != last)
  		{
  			ForwardIterator next = first;
  
  			while(++next != last)
  			{
  				if(*next < *first)
  					return next;
  
  				first = next;
  			}
  		}
  
  		return last;
  	}
  
  	template<typename ForwardIterator, typename Compare>
  	ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare compare)
  	{
  		if(first != last)
  		{
  			ForwardIterator next = first;
  
  			while(++next != last)
  			{
  				if(compare(*next, *first))
  					return next;
  
  				first = next;
  			}
  		}
  
  		return last;
  	}
  
  
  
  	/// merge
  	///
  	/// This function merges two sorted input sorted ranges into a result sorted range.
  	/// This merge is stable in that no element from the first range will be changed
  	/// in order relative to other elements from the first range.
  	///
  	template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
  	OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare compare)
  	{
  		while((first1 != last1) && (first2 != last2))
  		{
  			if(compare(*first2, *first1))
  			{
  				EASTL_VALIDATE_COMPARE(!compare(*first1, *first2)); // Validate that the compare function is sane.
  				*result = *first2;
  				++first2;
  			}
  			else
  			{
  				*result = *first1;
  				++first1;
  			}
  			++result;
  		}
  
  		// Check which list is empty and explicitly copy remaining items from the other list.
  		// For performance reasons, only a single copy operation is invoked to avoid the potential overhead
  		// introduced by chaining two copy operations together.  Even if a copy is of zero size there can
  		// be overhead from calling memmove with a zero size copy.
  		if (first1 == last1)
  		{
  			return eastl::copy(first2, last2, result);
  		}
  		else
  		{
  			return eastl::copy(first1, last1, result);
  		}
  	}
  
  	template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
  	inline OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
  	{
  		typedef eastl::less<typename eastl::iterator_traits<InputIterator1>::value_type> Less;
  
  		return eastl::merge<InputIterator1, InputIterator2, OutputIterator, Less>
  						   (first1, last1, first2, last2, result, Less());
  	}
  
  
  	//////////////////////////////////////////////////////////////////////////////
  	/// insertion_sort
  	///
  	/// insertion_sort is an O(n^2) stable sorting algorithm that starts at the
  	/// (k + 1) element and assumes the first (k) elements are sorted.
  	/// Then copy_backwards from (k + 1) to the begining any elements where the
  	/// (k + 1) element is less than [0, k] elements. The position of k when
  	/// (k + 1) element is not less than k is the sorted position of the (k + 1) element.
  	///
  	/// Example With Intermediate Steps:
  	/// (k + 1) == 2 : [3, 2, 1] -> [3, 3, 1] -> [2, 3, 1]
  	/// (k + 1) == 1 : [2, 3, 1] -> [2, 3, 3] -> [2, 2, 3] -> [1, 2, 3]
  	///              : [1, 2, 3]
  	template <typename BidirectionalIterator, typename StrictWeakOrdering>
  	void insertion_sort(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering compare)
  	{
  		typedef typename eastl::iterator_traits<BidirectionalIterator>::value_type value_type;
  
  		if (first != last)
  		{
  			BidirectionalIterator i = first;
  
  			for (++i; i != last; ++i)
  			{
  				value_type insertValue(eastl::move(*i));
  				BidirectionalIterator insertPosition = i;
  
  				for (BidirectionalIterator movePosition = i; movePosition != first && compare(insertValue, *(--movePosition)); --insertPosition)
  				{
  					EASTL_VALIDATE_COMPARE(!compare(*movePosition, insertValue));
  					*insertPosition = eastl::move(*movePosition);
  				}
  
  				*insertPosition = eastl::move(insertValue);
  			}
  		}
  	} // insertion_sort
  
  
  	template <typename BidirectionalIterator>
  	void insertion_sort(BidirectionalIterator first, BidirectionalIterator last)
  	{
  		typedef eastl::less<typename eastl::iterator_traits<BidirectionalIterator>::value_type> Less;
  
  		insertion_sort<BidirectionalIterator>(first, last, Less());
  
  	} // insertion_sort
  
  
  	/// shell_sort
  	///
  	/// Implements the ShellSort algorithm. This algorithm is a serious algorithm for larger 
  	/// data sets, as reported by Sedgewick in his discussions on QuickSort. Note that shell_sort
  	/// requires a random access iterator, which usually means an array (eg. vector, deque).
  	/// ShellSort has good performance with presorted sequences.
  	/// The term "shell" derives from the name of the inventor, David Shell.
  	///
  	/// To consider: Allow the user to specify the "h-sequence" array.
  	///
  	template <typename RandomAccessIterator, typename StrictWeakOrdering>
  	void shell_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering compare)
  	{
  		typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
  
  		// We use the Knuth 'h' sequence below, as it is easy to calculate at runtime. 
  		// However, possibly we are better off using a different sequence based on a table.
  		// One such sequence which averages slightly better than Knuth is:
  		//    1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 
  		//    64769, 146305, 260609, 587521, 1045505, 2354689, 4188161, 9427969, 16764929
  
  		if(first != last)
  		{
  			RandomAccessIterator iCurrent, iBack, iSorted, iInsertFirst;
  			difference_type      nSize  = last - first;
  			difference_type      nSpace = 1; // nSpace is the 'h' value of the ShellSort algorithm.
  
  			while(nSpace < nSize)
  				nSpace = (nSpace * 3) + 1; // This is the Knuth 'h' sequence: 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 
  
  			for(nSpace = (nSpace - 1) / 3; nSpace >= 1; nSpace = (nSpace - 1) / 3)  // Integer division is less than ideal.
  			{
  				for(difference_type i = 0; i < nSpace; i++)
  				{
  					iInsertFirst = first + i;
  
  					for(iSorted = iInsertFirst + nSpace; iSorted < last; iSorted += nSpace)
  					{
  						iBack = iCurrent = iSorted;
  						
  						for(; (iCurrent != iInsertFirst) && compare(*iCurrent, *(iBack -= nSpace)); iCurrent = iBack)
  						{
  							EASTL_VALIDATE_COMPARE(!compare(*iBack, *iCurrent)); // Validate that the compare function is sane.
  							eastl::iter_swap(iCurrent, iBack);
  						}
  					}
  				}
  			}
  		}
  	} // shell_sort
  
  	template <typename RandomAccessIterator>
  	inline void shell_sort(RandomAccessIterator first, RandomAccessIterator last)
  	{
  		typedef eastl::less<typename eastl::iterator_traits<RandomAccessIterator>::value_type> Less;
  
  		eastl::shell_sort<RandomAccessIterator, Less>(first, last, Less());
  	}
  
  
  
  	/// heap_sort
  	///
  	/// Implements the HeapSort algorithm. 
  	/// Note that heap_sort requires a random access iterator, which usually means 
  	/// an array (eg. vector, deque).
  	///
  	template <typename RandomAccessIterator, typename StrictWeakOrdering>
  	void heap_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering compare)
  	{
  		// We simply call our heap algorithms to do the work for us.
  		eastl::make_heap<RandomAccessIterator, StrictWeakOrdering>(first, last, compare);
  		eastl::sort_heap<RandomAccessIterator, StrictWeakOrdering>(first, last, compare);
  	}
  
  	template <typename RandomAccessIterator>
  	inline void heap_sort(RandomAccessIterator first, RandomAccessIterator last)
  	{
  		typedef eastl::less<typename eastl::iterator_traits<RandomAccessIterator>::value_type> Less;
  
  		eastl::heap_sort<RandomAccessIterator, Less>(first, last, Less());
  	}
  
  
  
  	namespace Internal
  	{
  		// Sorts a range whose initial (start - first) entries are already sorted.
  		// This function is a useful helper to the tim_sort function.
  		// This is the same as insertion_sort except that it has a start parameter which indicates
  		// where the start of the unsorted data is.
  		template <typename BidirectionalIterator, typename StrictWeakOrdering>
  		void insertion_sort_already_started(BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator start, StrictWeakOrdering compare)
  		{
  			typedef typename eastl::iterator_traits<BidirectionalIterator>::value_type value_type;
  
  			if (first != last) // if the range is non-empty...
  			{
  				BidirectionalIterator iCurrent, iNext, iSorted = start - 1;
  
  				for (++iSorted; iSorted != last; ++iSorted)
  				{
  					const value_type temp(*iSorted);
  
  					iNext = iCurrent = iSorted;
  
  					for (--iCurrent; (iNext != first) && compare(temp, *iCurrent); --iNext, --iCurrent)
  					{
  						EASTL_VALIDATE_COMPARE(!compare(*iCurrent, temp)); // Validate that the compare function is sane.
  						*iNext = *iCurrent;
  					}
  
  					*iNext = temp;
  				}
  			}
  		}
  	}
  
  
  
  	/// 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.
  	template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering, typename difference_type, int InsertionSortLimit>
  	class MergeSorter
  	{
  	public:
  		static void sort(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer, StrictWeakOrdering compare)
  		{
  			if (sort_impl(first, last, pBuffer, difference_type(0), compare) == RL_Buffer)
  			{
  				const difference_type nCount = last - first;
  				eastl::copy<T*, RandomAccessIterator>(pBuffer, pBuffer + nCount, first);
  			}
  			EASTL_DEV_ASSERT((eastl::is_sorted<RandomAccessIterator, StrictWeakOrdering>(first, last, compare)));
  		}
  
  	private:
  		static_assert(InsertionSortLimit > 1, "Sequences of length 1 are already sorted.  Use a larger value for InsertionSortLimit");
  
  		enum ResultLocation
  		{
  			RL_SourceRange,	// i.e. result is in the range defined by [first, last)
  			RL_Buffer,		// i.e. result is in pBuffer
  		};
  
  		// sort_impl
  		//
  		// This sort routine sorts the data in [first, last) and places the result in pBuffer or in the original range of the input.  The actual
  		// location of the data is indicated by the enum returned.
  		// 
  		// lastSortedEnd is used to specify a that data in the range [first, first + lastSortedEnd] is already sorted.  This information is used
  		// to avoid unnecessary merge sorting of already sorted data.  lastSortedEnd is a hint, and can be an under estimate of the sorted elements
  		// (i.e. it is legal to pass 0).
  		static ResultLocation sort_impl(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer, difference_type lastSortedEnd, StrictWeakOrdering compare)
  		{
  			const difference_type nCount = last - first;
  
  			if (lastSortedEnd < 1)
  			{
  				lastSortedEnd = eastl::is_sorted_until<RandomAccessIterator, StrictWeakOrdering>(first, last, compare) - first;
  			}
  
  			// Sort the region unless lastSortedEnd indicates it is already sorted.
  			if (lastSortedEnd < nCount)
  			{
  				// If the size is less than or equal to InsertionSortLimit use insertion sort instead of recursing further.
  				if (nCount <= InsertionSortLimit)
  				{
  					eastl::Internal::insertion_sort_already_started<RandomAccessIterator, StrictWeakOrdering>(first, last, first + lastSortedEnd, compare);
  					return RL_SourceRange;
  				}
  				else
  				{
  					const difference_type nMid = nCount / 2;
  
  					ResultLocation firstHalfLocation = RL_SourceRange;
  					// Don't sort the first half if it is already sorted.
  					if (lastSortedEnd < nMid)
  					{
  						firstHalfLocation = sort_impl(first, first + nMid, pBuffer, lastSortedEnd, compare);
  					}
  
  					ResultLocation secondHalfLocation = sort_impl(first + nMid, last, pBuffer + nMid, lastSortedEnd - nMid, compare);
  
  					return merge_halves(first, last, nMid, pBuffer, firstHalfLocation, secondHalfLocation, compare);
  				}
  			}
  			else
  			{
  				EASTL_DEV_ASSERT((eastl::is_sorted<RandomAccessIterator, StrictWeakOrdering>(first, last, compare)));
  				return RL_SourceRange;
  			}
  		}
  
  		// merge_halves
  		//
  		// Merge two sorted regions of elements.
  		// The inputs to this method effectively define two large buffers.  The variables 'firstHalfLocation' and 'secondHalfLocation' define where the data to be
  		// merged is located within the two buffers.  It is entirely possible that the two areas to be merged could be entirely located in either of the larger buffers.
  		// Upon returning the merged results will be in one of the two buffers (indicated by the return result).
  		static ResultLocation merge_halves(RandomAccessIterator first, RandomAccessIterator last, difference_type nMid, T* pBuffer, ResultLocation firstHalfLocation, ResultLocation secondHalfLocation, StrictWeakOrdering compare)
  		{
  			const difference_type nCount = last - first;
  			if (firstHalfLocation == RL_SourceRange)
  			{
  				if (secondHalfLocation == RL_SourceRange)
  				{
  					eastl::merge<RandomAccessIterator, RandomAccessIterator, T*, StrictWeakOrdering>(first, first + nMid, first + nMid, last, pBuffer, compare);
  					EASTL_DEV_ASSERT((eastl::is_sorted<T*, StrictWeakOrdering>(pBuffer, pBuffer + nCount, compare)));
  					return RL_Buffer;
  				}
  				else
  				{
  					eastl::copy(first, first + nMid, pBuffer);
  					eastl::merge<T*, T*, RandomAccessIterator, StrictWeakOrdering>(pBuffer, pBuffer + nMid, pBuffer + nMid, pBuffer + nCount, first, compare);
  					EASTL_DEV_ASSERT((eastl::is_sorted<RandomAccessIterator, StrictWeakOrdering>(first, last, compare)));
  					return RL_SourceRange;
  				}
  			}
  			else
  			{
  				if (secondHalfLocation == RL_SourceRange)
  				{
  					eastl::copy(first + nMid, last, pBuffer + nMid);
  					eastl::merge<T*, T*, RandomAccessIterator, StrictWeakOrdering>(pBuffer, pBuffer + nMid, pBuffer + nMid, pBuffer + nCount, first, compare);
  					EASTL_DEV_ASSERT((eastl::is_sorted<RandomAccessIterator, StrictWeakOrdering>(first, last, compare)));
  					return RL_SourceRange;
  				}
  				else
  				{
  					eastl::merge<T*, T*, RandomAccessIterator, StrictWeakOrdering>(pBuffer, pBuffer + nMid, pBuffer + nMid, pBuffer + nCount, first, compare);
  					EASTL_DEV_ASSERT((eastl::is_sorted<RandomAccessIterator, StrictWeakOrdering>(first, last, compare)));
  					return RL_SourceRange;
  				}
  			}
  		}
  
  	};
  
  
  	template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering>
  	void merge_sort_buffer(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer, StrictWeakOrdering compare)
  	{
  		typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
  		MergeSorter<RandomAccessIterator, T, StrictWeakOrdering, difference_type, 16>::sort(first, last, pBuffer, compare);
  	}
  
  	template <typename RandomAccessIterator, typename T>
  	inline void merge_sort_buffer(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer)
  	{
  		typedef eastl::less<typename eastl::iterator_traits<RandomAccessIterator>::value_type> Less;
  
  		eastl::merge_sort_buffer<RandomAccessIterator, T, Less>(first, last, pBuffer, Less());
  	}
  
  
  
  	/// merge_sort
  	///
  	/// Implements the MergeSort algorithm.
  	/// This algorithm allocates memory via the user-supplied allocator. Use merge_sort_buffer
  	/// function if you want a version which doesn't allocate memory.
  	/// Note that merge_sort requires a random access iterator, which usually means 
  	/// an array (eg. vector, deque).
  	/// 
  	template <typename RandomAccessIterator, typename Allocator, typename StrictWeakOrdering>
  	void merge_sort(RandomAccessIterator first, RandomAccessIterator last, Allocator& allocator, StrictWeakOrdering compare)
  	{
  		typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
  		typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
  
  		const difference_type nCount = last - first;
  
  		if(nCount > 1)
  		{
  			// We need to allocate an array of nCount value_type objects as a temporary buffer.
  			value_type* const pBuffer = (value_type*)allocate_memory(allocator, nCount * sizeof(value_type), EASTL_ALIGN_OF(value_type), 0);
  			eastl::uninitialized_fill(pBuffer, pBuffer + nCount, value_type());
  
  			eastl::merge_sort_buffer<RandomAccessIterator, value_type, StrictWeakOrdering>
  									(first, last, pBuffer, compare);
  
  			eastl::destruct(pBuffer, pBuffer + nCount);
  			EASTLFree(allocator, pBuffer, nCount * sizeof(value_type));
  		}
  	}
  
  	template <typename RandomAccessIterator, typename Allocator>
  	inline void merge_sort(RandomAccessIterator first, RandomAccessIterator last, Allocator& allocator)
  	{
  		typedef eastl::less<typename eastl::iterator_traits<RandomAccessIterator>::value_type> Less;
  
  		eastl::merge_sort<RandomAccessIterator, Allocator, Less>(first, last, allocator, Less());
  	}
  
  
  
  	/// partition
  	///
  	/// Implements the partition algorithm.
  	/// Rearranges the elements in the range [first, last), in such a way that all the elements 
  	/// for which pred returns true precede all those for which it returns false. The iterator 
  	/// returned points to the first element of the second group.
  	/// The relative ordering within each group is not necessarily the same as before the call. 
  	/// See function stable_partition for a function with a similar behavior and stability in 
  	/// the ordering.
  	/// 
  	/// To do: Implement a version that uses a faster BidirectionalIterator algorithm for the 
  	///        case that the iterator range is a bidirectional iterator instead of just an
  	///        input iterator (one direction).
  	///
  	template<typename InputIterator, typename Predicate>
  	InputIterator partition(InputIterator begin, InputIterator end, Predicate predicate)
  	{
  		if(begin != end) 
  		{
  			while(predicate(*begin))
  			{
  				if(++begin == end) 
  					return begin;
  			}
  
  			InputIterator middle = begin;
  
  			while(++middle != end)
  			{
  				if(predicate(*middle))
  				{
  					eastl::swap(*begin, *middle);
  					++begin;
  				}
  			}
  		}
  
  		return begin;
  	}
  
  	/// stable_partition
  	///
  	/// Performs the same function as @p partition() with the additional
  	/// guarantee that the relative ordering of elements in each group is
  	/// preserved.
  	template <typename ForwardIterator, typename Predicate>
  	ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred)
  	{
  		first = eastl::find_if_not(first, last, pred);
  
  		if (first == last)
  			return first;
  
  		typedef typename iterator_traits<ForwardIterator>::value_type value_type;
  
  		const auto requested_size = eastl::distance(first, last);
  
  		auto allocator = *get_default_allocator(0);
  		value_type* const buffer =
  		    (value_type*)allocate_memory(allocator, requested_size * sizeof(value_type), EASTL_ALIGN_OF(value_type), 0);
  		eastl::uninitialized_fill(buffer, buffer + requested_size, value_type());
  
  		ForwardIterator result1 = first;
  		value_type* result2 = buffer;
  
  		*result2 = eastl::move(*first);
  		++result2;
  		++first;
  		for (; first != last; ++first)
  		{
  			if (pred(*first))
  			{
  				*result1 = eastl::move(*first);
  				++result1;
  			}
  			else
  			{
  				*result2 = eastl::move(*first);
  				++result2;
  			}
  		}
  
  		eastl::copy(buffer, result2, result1);
  
  		eastl::destruct(buffer, buffer + requested_size);
  		EASTLFree(allocator, buffer, requested_size * sizeof(value_type));
  		
  		return result1;
  	}
  
  	/////////////////////////////////////////////////////////////////////
  	// quick_sort
  	//
  	// We do the "introspection sort" variant of quick sort which is now
  	// well-known and understood. You can read about this algorithm in
  	// many articles on quick sort, but briefly what it does is a median-
  	// of-three quick sort whereby the recursion depth is limited to a
  	// some value (after which it gives up on quick sort and switches to
  	// a heap sort) and whereby after a certain amount of sorting the 
  	// algorithm stops doing quick-sort and finishes the sorting via
  	// a simple insertion sort.
  	/////////////////////////////////////////////////////////////////////
  
  	#if (defined(EA_PROCESSOR_X86) || defined(EA_PROCESSOR_X86_64))
  		static const int kQuickSortLimit = 28; // For sorts of random arrays over 100 items, 28 - 32 have been found to be good numbers on x86.
  	#else
  		static const int kQuickSortLimit = 16; // It seems that on other processors lower limits are more beneficial, as they result in fewer compares.
  	#endif
  
  	namespace Internal
  	{
  		template <typename Size>
  		inline Size Log2(Size n)
  		{
  			int i;
  			for(i = 0; n; ++i)
  				n >>= 1;
  			return i - 1;
  		}
  
  		// To do: Investigate the speed of this bit-trick version of Log2.
  		//        It may work better on some platforms but not others.
  		//
  		// union FloatUnion {
  		//     float    f;
  		//     uint32_t i;
  		// };
  		// 
  		// inline uint32_t Log2(uint32_t x)
  		// {
  		//     const FloatInt32Union u = { x };
  		//     return (u.i >> 23) - 127;
  		// }
  	}
  
  	template <typename RandomAccessIterator, typename T>
  	inline RandomAccessIterator get_partition_impl(RandomAccessIterator first, RandomAccessIterator last, T&& pivotValue)
  	{
  		for(; ; ++first)
  		{
  			while(*first < pivotValue)
  			{
  				EASTL_VALIDATE_COMPARE(!(pivotValue < *first)); // Validate that the compare function is sane.
  				++first;
  			}
  			--last;
  
  			while(pivotValue < *last)
  			{
  				EASTL_VALIDATE_COMPARE(!(*last < pivotValue)); // Validate that the compare function is sane.
  				--last;
  			}
  
  			if(first >= last) // Random access iterators allow operator >=
  				return first;
  
  			eastl::iter_swap(first, last);
  		}
  	}
  
  	/// get_partition
  	///
  	/// This function takes const T& instead of T because T may have special alignment
  	/// requirements and some compilers (e.g. VC++) are don't respect alignment requirements
  	/// for function arguments.
  	///
  	template <typename RandomAccessIterator, typename T>
  	inline RandomAccessIterator get_partition(RandomAccessIterator first, RandomAccessIterator last, const T& pivotValue)
  	{
  		const T pivotCopy(pivotValue); // Need to make a temporary because the sequence below is mutating.
  		return get_partition_impl<RandomAccessIterator, const T&>(first, last, pivotCopy);
  	}
  
  	template <typename RandomAccessIterator, typename T>
  	inline RandomAccessIterator get_partition(RandomAccessIterator first, RandomAccessIterator last, T&& pivotValue)
  	{
  		// Note: unlike the copy-constructible variant of get_partition... we can't create a temporary const move-constructible object
  		return get_partition_impl<RandomAccessIterator, T&&>(first, last, eastl::move(pivotValue));
  	}
  
  	template <typename RandomAccessIterator, typename T, typename Compare>
  	inline RandomAccessIterator get_partition_impl(RandomAccessIterator first, RandomAccessIterator last, T&& pivotValue, Compare compare)
  	{
  		for(; ; ++first)
  		{
  			while(compare(*first, pivotValue))
  			{
  				EASTL_VALIDATE_COMPARE(!compare(pivotValue, *first)); // Validate that the compare function is sane.
  				++first;
  			}
  			--last;
  
  			while(compare(pivotValue, *last))
  			{
  				EASTL_VALIDATE_COMPARE(!compare(*last, pivotValue)); // Validate that the compare function is sane.
  				--last;
  			}
  
  			if(first >= last) // Random access iterators allow operator >=
  				return first;
  
  			eastl::iter_swap(first, last);
  		}
  	}
  
  	template <typename RandomAccessIterator, typename T, typename Compare> 
  	inline RandomAccessIterator get_partition(RandomAccessIterator first, RandomAccessIterator last, const T& pivotValue, Compare compare)
  	{
  		const T pivotCopy(pivotValue); // Need to make a temporary because the sequence below is mutating.
  		return get_partition_impl<RandomAccessIterator, const T&, Compare>(first, last, pivotCopy, compare);
  	}
  
  	template <typename RandomAccessIterator, typename T, typename Compare>
  	inline RandomAccessIterator get_partition(RandomAccessIterator first, RandomAccessIterator last, T&& pivotValue, Compare compare)
  	{
  		// Note: unlike the copy-constructible variant of get_partition... we can't create a temporary const move-constructible object
  		return get_partition_impl<RandomAccessIterator, T&&, Compare>(first, last, eastl::forward<T>(pivotValue), compare);
  	}
  
  
  	namespace Internal
  	{
  		// This function is used by quick_sort and is not intended to be used by itself. 
  		// This is because the implementation below makes an assumption about the input
  		// data that quick_sort satisfies but arbitrary data may not.
  		// There is a standalone insertion_sort function. 
  		template <typename RandomAccessIterator>
  		inline void insertion_sort_simple(RandomAccessIterator first, RandomAccessIterator last)
  		{
  			for(RandomAccessIterator current = first; current != last; ++current)
  			{
  				typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type value_type;
  
  				RandomAccessIterator end(current), prev(current);
  				value_type           value(eastl::forward<value_type>(*current));
  
  				for(--prev; value < *prev; --end, --prev) // We skip checking for (prev >= first) because quick_sort (our caller) makes this unnecessary.
  				{
  					EASTL_VALIDATE_COMPARE(!(*prev < value)); // Validate that the compare function is sane.
  					*end = eastl::forward<value_type>(*prev);
  				}
  
  				*end = eastl::forward<value_type>(value);
  			}
  		}
  
  
  		// This function is used by quick_sort and is not intended to be used by itself. 
  		// This is because the implementation below makes an assumption about the input
  		// data that quick_sort satisfies but arbitrary data may not.
  		// There is a standalone insertion_sort function. 
  		template <typename RandomAccessIterator, typename Compare>
  		inline void insertion_sort_simple(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
  		{
  			for(RandomAccessIterator current = first; current != last; ++current)
  			{
  				typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type value_type;
  
  				RandomAccessIterator end(current), prev(current);
  				value_type           value(eastl::forward<value_type>(*current));
  
  				for(--prev; compare(value, *prev); --end, --prev) // We skip checking for (prev >= first) because quick_sort (our caller) makes this unnecessary.
  				{
  					EASTL_VALIDATE_COMPARE(!compare(*prev, value)); // Validate that the compare function is sane.
  					*end = eastl::forward<value_type>(*prev);
  				}
  
  				*end = eastl::forward<value_type>(value);
  			}
  		}
  	} // namespace Internal
  
  
  	template <typename RandomAccessIterator>
  	inline void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
  	{
  		typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
  		typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
  
  		eastl::make_heap<RandomAccessIterator>(first, middle);
  
  		for(RandomAccessIterator i = middle; i < last; ++i)
  		{
  			if(*i < *first)
  			{
  				EASTL_VALIDATE_COMPARE(!(*first < *i)); // Validate that the compare function is sane.
  				value_type temp(eastl::forward<value_type>(*i));
  				*i = eastl::forward<value_type>(*first);
  				eastl::adjust_heap<RandomAccessIterator, difference_type, value_type>
  								  (first, difference_type(0), difference_type(middle - first), difference_type(0), eastl::forward<value_type>(temp));
  			}
  		}
  
  		eastl::sort_heap<RandomAccessIterator>(first, middle);
  	}
  
  
  	template <typename RandomAccessIterator, typename Compare>
  	inline void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare compare)
  	{
  		typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
  		typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
  
  		eastl::make_heap<RandomAccessIterator, Compare>(first, middle, compare);
  
  		for(RandomAccessIterator i = middle; i < last; ++i)
  		{
  			if(compare(*i, *first))
  			{
  				EASTL_VALIDATE_COMPARE(!compare(*first, *i)); // Validate that the compare function is sane.
  				value_type temp(eastl::forward<value_type>(*i));
  				*i = eastl::forward<value_type>(*first);
  				eastl::adjust_heap<RandomAccessIterator, difference_type, value_type, Compare>
  								  (first, difference_type(0), difference_type(middle - first), difference_type(0), eastl::forward<value_type>(temp), compare);
  			}
  		}
  
  		eastl::sort_heap<RandomAccessIterator, Compare>(first, middle, compare);
  	}
  
  
  	template<typename RandomAccessIterator>
  	inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
  	{
  		typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
  
  		while((last - first) > 5)
  		{
  			const value_type           midValue(eastl::median<value_type>(*first, *(first + (last - first) / 2), *(last - 1)));
  			const RandomAccessIterator midPos(eastl::get_partition<RandomAccessIterator, value_type>(first, last, midValue));
  
  			if(midPos <= nth)
  				first = midPos;
  			else
  				last = midPos;
  		}
  
  		eastl::insertion_sort<RandomAccessIterator>(first, last);
  	}
  
  
  	template<typename RandomAccessIterator, typename Compare>
  	inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare compare)
  	{
  		typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
  
  		while((last - first) > 5)
  		{
  			const value_type           midValue(eastl::median<value_type, Compare>(*first, *(first + (last - first) / 2), *(last - 1), compare));
  			const RandomAccessIterator midPos(eastl::get_partition<RandomAccessIterator, value_type, Compare>(first, last, midValue, compare));
  
  			if(midPos <= nth)
  				first = midPos;
  			else
  				last = midPos;
  		}
  
  		eastl::insertion_sort<RandomAccessIterator, Compare>(first, last, compare);
  	}
  
  
  	namespace Internal
  	{
  		EA_DISABLE_VC_WARNING(4702) // unreachable code
  		template <typename RandomAccessIterator, typename Size, typename PivotValueType>
  		inline void quick_sort_impl_helper(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount)
  		{
  			typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
  
  			while(((last - first) > kQuickSortLimit) && (kRecursionCount > 0))
  			{
  				const RandomAccessIterator position(eastl::get_partition<RandomAccessIterator, value_type>(first, last,
  					eastl::forward<PivotValueType>(eastl::median<value_type>(eastl::forward<value_type>(*first), eastl::forward<value_type>(*(first + (last - first) / 2)), eastl::forward<value_type>(*(last - 1))))));
  
  				eastl::Internal::quick_sort_impl_helper<RandomAccessIterator, Size, PivotValueType>(position, last, --kRecursionCount);
  				last = position;
  			}
  
  			if(kRecursionCount == 0)
  				eastl::partial_sort<RandomAccessIterator>(first, last, last);
  		}
  
  		template <typename RandomAccessIterator, typename Size, typename Compare, typename PivotValueType>
  		inline void quick_sort_impl_helper(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount, Compare compare)
  		{
  			typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
  
  			while(((last - first) > kQuickSortLimit) && (kRecursionCount > 0))
  			{
  				const RandomAccessIterator position(eastl::get_partition<RandomAccessIterator, value_type, Compare>(first, last,
  					eastl::forward<PivotValueType>(eastl::median<value_type, Compare>(eastl::forward<value_type>(*first), eastl::forward<value_type>(*(first + (last - first) / 2)), eastl::forward<value_type>(*(last - 1)), compare)), compare));
  
  				eastl::Internal::quick_sort_impl_helper<RandomAccessIterator, Size, Compare, PivotValueType>(position, last, --kRecursionCount, compare);
  				last = position;
  			}
  
  			if(kRecursionCount == 0)
  				eastl::partial_sort<RandomAccessIterator, Compare>(first, last, last, compare);
  		}
  		EA_RESTORE_VC_WARNING()
  
  		template <typename RandomAccessIterator, typename Size>
  		inline void quick_sort_impl(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount,
  			typename eastl::enable_if<eastl::is_copy_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value>::type* = 0)
  		{
  			typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
  
  			// copy constructors require const value_type
  			quick_sort_impl_helper<RandomAccessIterator, Size, const value_type>(first, last, kRecursionCount);
  		}
  
  		template <typename RandomAccessIterator, typename Size>
  		inline void quick_sort_impl(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount,
  			typename eastl::enable_if<eastl::is_move_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value
  			&& !eastl::is_copy_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value>::type* = 0)
  		{
  			typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
  
  			// move constructors require non-const value_type
  			quick_sort_impl_helper<RandomAccessIterator, Size, value_type>(first, last, kRecursionCount);
  		}
  
  		template <typename RandomAccessIterator, typename Size, typename Compare>
  		inline void quick_sort_impl(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount, Compare compare,
  			typename eastl::enable_if<eastl::is_copy_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value>::type* = 0)
  		{
  			typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
  
  			// copy constructors require const value_type
  			quick_sort_impl_helper<RandomAccessIterator, Size, Compare, const value_type>(first, last, kRecursionCount, compare);
  		}
  
  		template <typename RandomAccessIterator, typename Size, typename Compare>
  		inline void quick_sort_impl(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount, Compare compare,
  			typename eastl::enable_if<eastl::is_move_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value
  			&& !eastl::is_copy_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value>::type* = 0)
  		{
  			typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
  
  			// move constructors require non-const value_type
  			quick_sort_impl_helper<RandomAccessIterator, Size, Compare, value_type>(first, last, kRecursionCount, compare);
  		}
  	}
  
  
  	/// quick_sort
  	///
  	/// This is an unstable sort.
  	/// quick_sort sorts the elements in [first, last) into ascending order, 
  	/// meaning that if i and j are any two valid iterators in [first, last) 
  	/// such that i precedes j, then *j is not less than *i. quick_sort is not 
  	/// guaranteed to be stable. That is, suppose that *i and *j are equivalent: 
  	/// neither one is less than the other. It is not guaranteed that the 
  	/// relative order of these two elements will be preserved by sort.
  	///
  	/// We implement the "introspective" variation of quick-sort. This is 
  	/// considered to be the best general-purpose variant, as it avoids 
  	/// worst-case behaviour and optimizes the final sorting stage by 
  	/// switching to an insertion sort.
  	///
  	template <typename RandomAccessIterator>
  	void quick_sort(RandomAccessIterator first, RandomAccessIterator last)
  	{
  		typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
  
  		if(first != last)
  		{
  			eastl::Internal::quick_sort_impl<RandomAccessIterator, difference_type>(first, last, 2 * Internal::Log2(last - first));
  
  			if((last - first) > (difference_type)kQuickSortLimit)
  			{
  				eastl::insertion_sort<RandomAccessIterator>(first, first + kQuickSortLimit);
  				eastl::Internal::insertion_sort_simple<RandomAccessIterator>(first + kQuickSortLimit, last);
  			}
  			else
  				eastl::insertion_sort<RandomAccessIterator>(first, last);
  		}
  	}
  
  
  	template <typename RandomAccessIterator, typename Compare>
  	void quick_sort(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
  	{
  		typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
  
  		if(first != last)
  		{
  			eastl::Internal::quick_sort_impl<RandomAccessIterator, difference_type, Compare>(first, last, 2 * Internal::Log2(last - first), compare);
  
  			if((last - first) > (difference_type)kQuickSortLimit)
  			{
  				eastl::insertion_sort<RandomAccessIterator, Compare>(first, first + kQuickSortLimit, compare);
  				eastl::Internal::insertion_sort_simple<RandomAccessIterator, Compare>(first + kQuickSortLimit, last, compare);
  			}
  			else
  				eastl::insertion_sort<RandomAccessIterator, Compare>(first, last, compare);
  		}
  	}
  
  
  
  
  	namespace Internal
  	{
  		// Portions of the tim_sort code were originally written by Christopher Swenson.
  		// https://github.com/swenson/sort
  		// All code in this repository, unless otherwise specified, is hereby licensed under the 
  		// MIT Public License: Copyright (c) 2010 Christopher Swenson
  
  		const intptr_t kTimSortStackSize = 64; // Question: What's the upper-limit size requirement for this?
  
  		struct tim_sort_run
  		{
  			intptr_t start;
  			intptr_t length;
  		};
  
  
  		// EASTL_COUNT_LEADING_ZEROES
  		//
  		// Count leading zeroes in an integer.
  		//
  		#ifndef EASTL_COUNT_LEADING_ZEROES
  			#if   defined(__GNUC__)
  				#if (EA_PLATFORM_PTR_SIZE == 8)
  					#define EASTL_COUNT_LEADING_ZEROES __builtin_clzll
  				#else
  					#define EASTL_COUNT_LEADING_ZEROES __builtin_clz
  				#endif
  			#endif
  
  			#ifndef EASTL_COUNT_LEADING_ZEROES
  				static inline int eastl_count_leading_zeroes(uint64_t x)
  				{
  					if(x)
  					{
  						int n = 0;
  						if(x & UINT64_C(0xFFFFFFFF00000000)) { n += 32; x >>= 32; }
  						if(x & 0xFFFF0000)                   { n += 16; x >>= 16; }
  						if(x & 0xFFFFFF00)                   { n +=  8; x >>=  8; }
  						if(x & 0xFFFFFFF0)                   { n +=  4; x >>=  4; }
  						if(x & 0xFFFFFFFC)                   { n +=  2; x >>=  2; }
  						if(x & 0xFFFFFFFE)                   { n +=  1;           }
  						return 63 - n;
  					}
  					return 64;
  				}
  
  				static inline int eastl_count_leading_zeroes(uint32_t x)
  				{
  					if(x)
  					{
  						int n = 0;
  						if(x <= 0x0000FFFF) { n += 16; x <<= 16; }
  						if(x <= 0x00FFFFFF) { n +=  8; x <<=  8; }
  						if(x <= 0x0FFFFFFF) { n +=  4; x <<=  4; }
  						if(x <= 0x3FFFFFFF) { n +=  2; x <<=  2; }
  						if(x <= 0x7FFFFFFF) { n +=  1;           }
  						return n;
  					}
  					return 32;
  				}
  
  				#define EASTL_COUNT_LEADING_ZEROES eastl_count_leading_zeroes
  			#endif
  		#endif
  
  
  		// reverse_elements
  		//
  		// Reverses the range [first + start, first + start + size)
  		// To consider: Use void eastl::reverse(BidirectionalIterator first, BidirectionalIterator last);
  		//
  		template <typename RandomAccessIterator>
  		void reverse_elements(RandomAccessIterator first, intptr_t start, intptr_t end)
  		{
  			while(start < end)
  			{
  				eastl::swap(*(first + start), *(first + end));
  				++start;
  				--end;
  			}
  		}
  
  
  		// tim_sort_count_run
  		//
  		// Finds the length of a run which is already sorted (either up or down).
  		// If the run is in reverse order, this function puts it in regular order.
  		//
  		template <typename RandomAccessIterator, typename StrictWeakOrdering>
  		intptr_t tim_sort_count_run(const RandomAccessIterator first, const intptr_t start, const intptr_t size, StrictWeakOrdering compare)
  		{
  			if((size - start) > 1) // If there is anything in the set...
  			{
  				intptr_t curr = (start + 2);
  				
  				if(!compare(*(first + start + 1), *(first + start))) // If (first[start + 1] >= first[start]) (If the run is increasing) ...
  				{
  					for(;; ++curr)
  					{
  						if(curr >= (size - 1)) // If we are at the end of the data... this run is done.
  							break;
  
  						if(compare(*(first + curr), *(first + curr - 1))) // If this item is not in order... this run is done.
  							break;
  					}
  				}
  				else  // Else it is decreasing.
  				{
  					for(;; ++curr)
  					{
  						if(curr >= (size - 1))  // If we are at the end of the data... this run is done.
  							break;
  
  						if(!compare(*(first + curr), *(first + curr - 1)))  // If this item is not in order... this run is done.
  							break;                                          // Note that we intentionally compare against <= 0 and not just < 0. This is because 
  					}                                                       // The reverse_elements call below could reverse two equal elements and break our stability requirement.
  
  					reverse_elements(first, start, curr - 1);
  				}
  
  				return (curr - start);
  			}
  
  			// Else we have just one item in the set.       
  			return 1;
  		}
  
  
  		// Input   Return
  		// --------------
  		//  64      32
  		//  65      33
  		//  66      33
  		//  67      34
  		//  68      34
  		// ...
  		// 125      63
  		// 126      63
  		// 127      64
  		// 128      32
  		// 129      33
  		// 130      33
  		// 131      33
  		// 132      33
  		// 133      34
  		// 134      34
  		// 135      34
  		// 136      34
  		// 137      35
  		// ...
  		//
  		// This function will return a value that is always in the range of [32, 64].
  		//
  		static inline intptr_t timsort_compute_minrun(intptr_t size)
  		{
  			const int32_t  top_bit = (int32_t)((sizeof(intptr_t) * 8) - EASTL_COUNT_LEADING_ZEROES((uintptr_t)size));
  			const int32_t  shift   = (top_bit > 6) ? (top_bit - 6) : 0;
  			const intptr_t mask    = (intptr_t(1) << shift) - 1;
  				  intptr_t minrun  = (intptr_t)(size >> shift);
  
  			if(mask & size)
  				++minrun;
  
  			return minrun;
  		}
  
  
  		template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering>
  		void tim_sort_merge(RandomAccessIterator first, const tim_sort_run* run_stack, const intptr_t stack_curr, 
  							T* pBuffer, StrictWeakOrdering compare)
  		{
  			const intptr_t A    = run_stack[stack_curr - 2].length;
  			const intptr_t B    = run_stack[stack_curr - 1].length;
  			const intptr_t curr = run_stack[stack_curr - 2].start;
  
  			EASTL_DEV_ASSERT((A < 10000000) && (B < 10000000) && (curr < 10000000)); // Sanity check.
  
  			if(A < B) // If the first run is shorter than the second run... merge left.
  			{
  				// Copy to another location so we have room in the main array to put the sorted items.
  				eastl::copy(first + curr, first + curr + A, pBuffer);
  
  				#if EASTL_DEV_DEBUG
  					typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type value_type;
  
  					for(intptr_t i = 0; i < A; i++)
  						*(first + curr + i) = value_type();
  				#endif
  
  				intptr_t i = 0;
  				intptr_t j = curr + A;
  				
  				for(intptr_t k = curr; k < curr + A + B; k++)
  				{
  					if((i < A) && (j < (curr + A + B)))
  					{
  						if(!compare(*(first + j), *(pBuffer + i))) // If (first[j] >= pBuffer[i])...
  							*(first + k) = *(pBuffer + i++);
  						else
  							*(first + k) = *(first + j++);
  					}
  					else if(i < A)
  						*(first + k) = *(pBuffer + i++);
  					else
  						*(first + k) = *(first + j++);
  				}
  			}
  			else // Else the second run is equal or shorter... merge right.
  			{
  				eastl::copy(first + curr + A, first + curr + A + B, pBuffer);
  
  				intptr_t i = B - 1;
  				intptr_t j = curr + A - 1;
  				
  				for(intptr_t k = curr + A + B - 1; k >= curr; k--)
  				{
  					if((i >= 0) && (j >= curr))
  					{
  						if(compare(*(pBuffer + i), *(first + j))) // If (pBuffer[i] < first[j]) ...
  							*(first + k) = *(first + j--);
  						else
  							*(first + k) = *(pBuffer + i--);
  					}
  					else if(i >= 0)
  						*(first + k) = *(pBuffer + i--);
  					else
  						*(first + k) = *(first + j--);
  				}
  			}
  		}
  
  
  		// See the timsort.txt file for an explanation of this function.
  		//
  		// ------------------------------------------------------------------------
  		// What turned out to be a good compromise maintains two invariants on the
  		// stack entries, where A, B and C are the lengths of the three righmost 
  		// not-yet merged slices:
  		//    1.  A > B+C
  		//    2.  B > C
  		// ------------------------------------------------------------------------
  		//
  		static inline bool timsort_check_invariant(tim_sort_run* run_stack, const intptr_t stack_curr)
  		{
  			// To do: Optimize this for the most common type of values.
  			if(stack_curr > 2)
  			{
  				const intptr_t A = run_stack[stack_curr - 3].length;
  				const intptr_t B = run_stack[stack_curr - 2].length;
  				const intptr_t C = run_stack[stack_curr - 1].length;
  
  				EASTL_DEV_ASSERT((A < 10000000) && (B < 10000000) && (C < 10000000)); // Sanity check.
  
  				if((A <= (B + C)) || (B <= C))
  					return true; // Merge the right-most runs.
  			}
  			else if(stack_curr == 2)
  			{
  				const intptr_t A = run_stack[stack_curr - 2].length;
  				const intptr_t B = run_stack[stack_curr - 1].length;
  
  				EASTL_DEV_ASSERT((A < 10000000) && (B < 10000000)); // Sanity check.
  
  				if(A <= B)
  					return true; // Merge the right-most runs.
  			}
  
  			return false; // Don't merge the right-most runs.
  		}
  
  
  		template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering>
  		intptr_t tim_sort_collapse(RandomAccessIterator first, tim_sort_run* run_stack, intptr_t stack_curr, 
  								   T* pBuffer, const intptr_t size, StrictWeakOrdering compare)
  		{
  			// If the run_stack only has one thing on it, we are done with the collapse.
  			while(stack_curr > 1)
  			{
  				// If this is the last merge, just do it.
  				if((stack_curr == 2) && ((run_stack[0].length + run_stack[1].length) == size))
  				{
  					tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, compare);
  					run_stack[0].length += run_stack[1].length;
  					stack_curr--;
  
  					#if EASTL_DEV_DEBUG
  						memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr]));
  					#endif
  
  					break;
  				}
  				// Check if the invariant is off for a run_stack of 2 elements.
  				else if((stack_curr == 2) && (run_stack[0].length <= run_stack[1].length))
  				{
  					tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, compare);
  					run_stack[0].length += run_stack[1].length;
  					stack_curr--;
  
  					#if EASTL_DEV_DEBUG
  						memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr]));
  					#endif
  
  					break;
  				}
  				else if (stack_curr == 2)
  					break;
  
  				const intptr_t A = run_stack[stack_curr - 3].length;
  				const intptr_t B = run_stack[stack_curr - 2].length;
  				const intptr_t C = run_stack[stack_curr - 1].length;
  				
  				if(A <= (B + C)) // Check first invariant.
  				{
  					if(A < C)
  					{
  						tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr - 1, pBuffer, compare);
  
  						stack_curr--;
  						run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length;   // Merge A and B.
  						run_stack[stack_curr - 1] = run_stack[stack_curr];
  
  						#if EASTL_DEV_DEBUG
  							EASTL_DEV_ASSERT((run_stack[stack_curr - 2].start + run_stack[stack_curr - 2].length) <= size);
  							EASTL_DEV_ASSERT((run_stack[stack_curr - 1].start + run_stack[stack_curr - 1].length) <= size);
  							memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr]));
  						#endif
  					}
  					else
  					{
  						tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, compare);                  // Merge B and C.
  
  						stack_curr--;
  						run_stack[stack_curr - 1].length += run_stack[stack_curr].length;
  
  						#if EASTL_DEV_DEBUG
  							EASTL_DEV_ASSERT((run_stack[stack_curr - 1].start + run_stack[stack_curr - 1].length) <= size);
  							memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr]));
  						#endif
  					}
  				}
  				else if(B <= C) // Check second invariant
  				{
  					tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, compare);
  
  					stack_curr--;
  					run_stack[stack_curr - 1].length += run_stack[stack_curr].length;       // Merge B and C.
  
  					#if EASTL_DEV_DEBUG
  						EASTL_DEV_ASSERT((run_stack[stack_curr - 1].start + run_stack[stack_curr - 1].length) <= size);
  						memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr]));
  					#endif
  				}
  				else
  					break;
  			}
  
  			return stack_curr;
  		}
  
  
  		// tim_sort_add_run
  		//
  		// Return true if the sort is done.
  		//
  		template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering>
  		bool tim_sort_add_run(tim_sort_run* run_stack, RandomAccessIterator first, T* pBuffer, const intptr_t size, const intptr_t minrun, 
  							  intptr_t& len, intptr_t& run, intptr_t& curr, intptr_t& stack_curr, StrictWeakOrdering compare)
  		{
  			len = tim_sort_count_run<RandomAccessIterator, StrictWeakOrdering>(first, curr, size, compare); // This will count the length of the run and reverse the run if it is backwards.
  			run = minrun;
  
  			if(run < minrun)            // Always make runs be of minrun length (we'll sort the additional data as needed below)
  			   run = minrun;
  
  			if(run > (size - curr))     // But if there isn't minrun data remaining, just sort what's remaining.
  			   run = (size - curr);
  
  			if(run > len)               // If there is any additional data we want to sort to bring up the run length to minrun.
  			{
  				insertion_sort_already_started<RandomAccessIterator, StrictWeakOrdering>(first + curr, first + curr + run, first + curr + len, compare);
  				len = run;
  			}
  
  			// At this point, run will be equal to minrun or will go to the end of our data.
  			// Add this run to our stack of runs.
  			EASTL_DEV_ASSERT(stack_curr < kTimSortStackSize);
  			EASTL_DEV_ASSERT((curr >= 0) && (curr < size) && ((curr + len) <= size));
  
  			run_stack[stack_curr].start  = curr;
  			run_stack[stack_curr].length = len;
  			stack_curr++;
  
  			// Move to the beginning of the next run in the data.
  			curr += len;
  
  			if(curr == size)    // If we have hit the end of the data...
  			{
  				while(stack_curr > 1) // If there is any more than one run... (else all the data is sorted)
  				{
  					tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, compare);
  
  					run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length;
  					stack_curr--;
  
  					#if EASTL_DEV_DEBUG
  						EASTL_DEV_ASSERT((run_stack[stack_curr - 1].start + run_stack[stack_curr - 1].length) <= size);
  						memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr]));
  					#endif
  				}
  
  				return true; // We are done with sorting.
  			}
  
  			return false;
  		}
  
  	} // namespace Internal
  
  
  	// tim_sort_buffer
  	//
  	/// This is a stable sort.
  	// Implements the tim-sort sorting algorithm with a user-provided scratch buffer.
  	// http://en.wikipedia.org/wiki/Timsort
  	// This sort is the fastest sort when sort stability (maintaining order of equal values) is required and
  	// data sets are non-trivial (size >= 15). It's also the fastest sort (e.g. faster than quick_sort) for 
  	// the case that at at least half your data is already sorted. Otherwise, eastl::quick_sort is about 10% 
  	// faster than tim_sort_buffer but is not a stable sort. There are some reports that tim_sort outperforms
  	// quick_sort but most of these aren't taking into account that optimal quick_sort implementations use
  	// a hybrid approach called "introsort" (http://en.wikipedia.org/wiki/Introsort) which improves quick_sort
  	// considerably in practice.
  	//
  	// Strengths:
  	//     - Fastest stable sort for most sizes of data.
  	//     - Fastest sort for containers of data already mostly sorted.
  	//     - Simpler to understand than quick_sort.
  	//
  	// Weaknesses:
  	//     - User must provide a scratch buffer, otherwise the buffer is dynamically allocated during runtime.
  	//     - Not as fast as quick_sort for the general case of randomized data.
  	//     - Requires a RandomAccessIterator; thus must be on an array container type and not a list container type.
  	//     - Uses a lot of code to implement; thus it's not great when there is little room for more code.
  	//
  	// The pBuffer parameter must hold at least ((last-first)/2) elements (i.e. half the elements of the container).
  	// This minimum size is a worst-case size requirement, but handles all possible cases. pBuffer is just a scratch
  	// buffer and is not needed after the return of this function, and doesn't need to be seeded with any particular
  	// values upon entering this function.
  	//
  	// Example usage:
  	//     int intArray[64];
  	//     int buffer[32];
  	//     ...
  	//     tim_sort_buffer(intArray, intArray + 64, buffer);
  	//
  	template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering>
  	void tim_sort_buffer(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer, StrictWeakOrdering compare)
  	{
  		using namespace Internal;
  
  		// To consider: Convert the implementation to use first/last instead of first/size.
  		const intptr_t size = (intptr_t)(last - first);
  
  		if(size < 64)
  			insertion_sort_already_started(first, first + size, first + 1, compare);
  		else
  		{
  			tim_sort_run   run_stack[kTimSortStackSize];
  			intptr_t       stack_curr = 0;
  			intptr_t       len, run;
  			intptr_t       curr = 0;
  			const intptr_t minrun = timsort_compute_minrun(size);
  
  			#if EASTL_DEV_DEBUG
  				memset(run_stack, 0, sizeof(run_stack));
  			#endif
  
  			if(tim_sort_add_run<RandomAccessIterator, T, StrictWeakOrdering>(run_stack, first, pBuffer, size, minrun, len, run, curr, stack_curr, compare))
  				return;
  			if(tim_sort_add_run<RandomAccessIterator, T, StrictWeakOrdering>(run_stack, first, pBuffer, size, minrun, len, run, curr, stack_curr, compare))
  				return;
  			if(tim_sort_add_run<RandomAccessIterator, T, StrictWeakOrdering>(run_stack, first, pBuffer, size, minrun, len, run, curr, stack_curr, compare))
  				return;
  
  			for(;;)
  			{
  				if(timsort_check_invariant(run_stack, stack_curr))
  					stack_curr = tim_sort_collapse<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, size, compare);
  				else
  				{
  					if(tim_sort_add_run<RandomAccessIterator, T, StrictWeakOrdering>(run_stack, first, pBuffer, size, minrun, len, run, curr, stack_curr, compare))
  						break;
  				}
  			}
  		}
  	}
  
  
  	template <typename RandomAccessIterator, typename T>
  	inline void tim_sort_buffer(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer)
  	{
  		typedef eastl::less<T> Less;
  
  		eastl::tim_sort_buffer<RandomAccessIterator, T, Less>(first, last, pBuffer, Less());
  	}
  
  
  
  
  	/// radix_sort
  	///
  	/// Implements a classic LSD (least significant digit) radix sort.
  	/// See http://en.wikipedia.org/wiki/Radix_sort.
  	/// This sort requires that the sorted data be of a type that has a member
  	/// radix_type typedef and an mKey member of that type. The type must be
  	/// an integral type. This limits what can be sorted, but radix_sort is 
  	/// very fast -- typically faster than any other sort.
  	/// For example:
  	///     struct Sortable {
  	///         typedef int radix_type;
  	///         radix_type mKey;
  	///         // User data goes here, or the user can inherit from Sortable.
  	///     };
  	/// or, more generally:
  	///     template <typname Integer>
  	///     struct Sortable {
  	///         typedef Integer radix_type;
  	///         Integer mKey;
  	///     };
  	/// 
  	/// Example usage:
  	///     struct Element {
  	///         typedef uint16_t radix_type;
  	///         uint16_t mKey;
  	///         uint16_t mUserData;
  	///     };
  	///
  	///     Element elementArray[100];
  	///     Element buffer[100];
  	///
  	///     radix_sort<Element*, extract_radix_key<Element> >(elementArray, elementArray + 100, buffer);
  	///
  	/// To consider: A static linked-list implementation may be faster than the version here.
  
  	namespace Internal
  	{
  		/// extract_radix_key
  		///
  		/// Default radix sort integer value reader. It expects the sorted elements 
  		/// to have an integer member of type radix_type and of name "mKey". 
  		///
  		template <typename Node>
  		struct extract_radix_key
  		{
  			typedef typename Node::radix_type radix_type;
  
  			const radix_type operator()(const Node& x) const
  				{ return x.mKey; }
  		};
  
  		// The radix_sort implementation uses two optimizations that are not part of a typical radix sort implementation.
  		// 1. Computing a histogram (i.e. finding the number of elements per bucket) for the next pass is done in parallel with the loop that "scatters"
  		//    elements in the current pass.  The advantage is that it avoids the memory traffic / cache pressure of reading keys in a separate operation.
  		//    Note: It would also be possible to compute all histograms in a single pass.  However, that would increase the amount of stack space used and
  		//    also increase cache pressure slightly.  However, it could still be faster under some situations.
  		// 2. If all elements are mapped to a single bucket, then there is no need to perform a scatter operation.  Instead the elements are left in place
  		//    and only copied if they need to be copied to the final output buffer.
  		template <typename RandomAccessIterator, typename ExtractKey, int DigitBits, typename IntegerType>
  		void radix_sort_impl(RandomAccessIterator first,
  			RandomAccessIterator last,
  			RandomAccessIterator buffer,
  			ExtractKey extractKey,
  			IntegerType)
  		{
  			RandomAccessIterator srcFirst = first;
  			constexpr size_t numBuckets = 1 << DigitBits;
  			constexpr IntegerType bucketMask = numBuckets - 1;
  
  			// The alignment of this variable isn't required; it merely allows the code below to be faster on some platforms.
  			uint32_t EA_PREFIX_ALIGN(EASTL_PLATFORM_PREFERRED_ALIGNMENT) bucketSize[numBuckets];
  			uint32_t EA_PREFIX_ALIGN(EASTL_PLATFORM_PREFERRED_ALIGNMENT) bucketPosition[numBuckets];
  
  			RandomAccessIterator temp;
  			uint32_t i;
  
  			bool doSeparateHistogramCalculation = true;
  			uint32_t j;
  			for (j = 0; j < (8 * sizeof(IntegerType)); j += DigitBits)
  			{
  				if (doSeparateHistogramCalculation)
  				{
  					memset(bucketSize, 0, sizeof(bucketSize));
  					// Calculate histogram for the first scatter operation
  					for (temp = srcFirst; temp != last; ++temp)
  						++bucketSize[(extractKey(*temp) >> j) & bucketMask];
  				}
  
  				// If a single bucket contains all of the elements, then don't bother redistributing all elements to the
  				// same bucket.
  				if (bucketSize[((extractKey(*srcFirst) >> j) & bucketMask)] == uint32_t(last - srcFirst))
  				{
  					// Set flag to ensure histogram is computed for next digit position.
  					doSeparateHistogramCalculation = true;
  				}
  				else
  				{
  					// The histogram is either not needed or it will be calculated in parallel with the scatter operation below for better cache efficiency.
  					doSeparateHistogramCalculation = false;
  
  					// If this is the last digit position, then don't calculate a histogram
  					if (j == (8 * sizeof(IntegerType) - DigitBits))
  					{
  						bucketPosition[0] = 0;
  						for (i = 0; i < numBuckets - 1; i++)
  						{
  							bucketPosition[i + 1] = bucketPosition[i] + bucketSize[i];
  						}
  
  						for (temp = srcFirst; temp != last; ++temp)
  						{
  							IntegerType key = extractKey(*temp);
  							const size_t digit = (key >> j) & bucketMask;
  							buffer[bucketPosition[digit]++] = *temp;
  						}
  					}
  					// Compute the histogram while performing the scatter operation
  					else
  					{
  						bucketPosition[0] = 0;
  						for (i = 0; i < numBuckets - 1; i++)
  						{
  							bucketPosition[i + 1] = bucketPosition[i] + bucketSize[i];
  							bucketSize[i] = 0;	// Clear the bucket for the next pass
  						}
  
  						uint32_t jNext = j + DigitBits;
  						for (temp = srcFirst; temp != last; ++temp)
  						{
  							IntegerType key = extractKey(*temp);
  							const size_t digit = (key >> j) & bucketMask;
  							buffer[bucketPosition[digit]++] = *temp;
  
  							// Update histogram for the next scatter operation
  							++bucketSize[(extractKey(*temp) >> jNext) & bucketMask];
  						}
  					}
  
  					last = buffer + (last - srcFirst);
  					temp = srcFirst;
  					srcFirst = buffer;
  					buffer = temp;
  				}
  			}
  
  			if (srcFirst != first)
  			{
  				// Copy values back into the expected buffer
  				for (temp = srcFirst; temp != last; ++temp)
  					*buffer++ = *temp;
  			}
  		}
  	} // namespace Internal
  
  	template <typename RandomAccessIterator, typename ExtractKey, int DigitBits = 8>
  	void radix_sort(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator buffer)
  	{
  		static_assert(DigitBits > 0, "DigitBits must be > 0");
  		static_assert(DigitBits <= (sizeof(typename ExtractKey::radix_type) * 8), "DigitBits must be <= the size of the key (in bits)");
  		eastl::Internal::radix_sort_impl<RandomAccessIterator, ExtractKey, DigitBits>(first, last, buffer, ExtractKey(), typename ExtractKey::radix_type());
  	}
  
  
  
  	/// comb_sort
  	///
  	/// This is an unstable sort.
  	/// Implements the CombSort algorithm; in particular, implements the CombSort11 variation 
  	/// of the CombSort algorithm, based on the reference to '11' in the implementation.
  	///
  	/// To consider: Use a comb sort table instead of the '((nSpace * 10) + 3) / 13' expression.
  	///              Ideal tables can be found on the Internet by looking up "comb sort table".
  	///
  	template <typename ForwardIterator, typename StrictWeakOrdering>
  	void comb_sort(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare)
  	{
  		typedef typename eastl::iterator_traits<ForwardIterator>::difference_type difference_type;
  
  		ForwardIterator iCurrent, iNext;
  		difference_type length = eastl::distance(first, last);
  		difference_type nSpace = length;
  
  		for(bool bSwapped = false; (nSpace > 1) || bSwapped; )
  		{
  			nSpace = ((nSpace * 10) + 3) / 13; // Integer division is less than ideal.
  
  			if((nSpace == 9) || (nSpace == 10))
  				nSpace = 11;
  
  			iCurrent = iNext = first;
  			eastl::advance(iNext, nSpace);
  			
  			for(bSwapped = false; iNext != last; iCurrent++, iNext++)
  			{
  				if(compare(*iNext, *iCurrent))
  				{
  					EASTL_VALIDATE_COMPARE(!compare(*iCurrent, *iNext)); // Validate that the compare function is sane.
  					eastl::iter_swap(iCurrent, iNext);
  					bSwapped = true;
  				}
  			}
  		}
  	} // comb_sort
  
  	template <typename ForwardIterator>
  	inline void comb_sort(ForwardIterator first, ForwardIterator last)
  	{
  		typedef eastl::less<typename eastl::iterator_traits<ForwardIterator>::value_type> Less;
  
  		eastl::comb_sort<ForwardIterator, Less>(first, last, Less());
  	}
  
  
  
  
  	/// bubble_sort
  	///
  	/// This is a stable sort.
  	/// Implements the BubbleSort algorithm. This algorithm is only useful for 
  	/// small range sizes, such as 10 or less items. You may be better off using
  	/// insertion_sort for cases where bubble_sort works.
  	///
  	namespace Internal
  	{
  		template <typename ForwardIterator, typename StrictWeakOrdering>
  		void bubble_sort_impl(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare, EASTL_ITC_NS::forward_iterator_tag)
  		{
  			ForwardIterator iCurrent, iNext;
  
  			while(first != last)
  			{
  				iNext = iCurrent = first;
  				
  				for(++iNext; iNext != last; iCurrent = iNext, ++iNext) 
  				{
  					if(compare(*iNext, *iCurrent))
  					{
  						EASTL_VALIDATE_COMPARE(!compare(*iCurrent, *iNext)); // Validate that the compare function is sane.
  						eastl::iter_swap(iCurrent, iNext);
  					}
  				}
  				last = iCurrent;
  			}
  		}
  
  		template <typename BidirectionalIterator, typename StrictWeakOrdering>
  		void bubble_sort_impl(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering compare, EASTL_ITC_NS::bidirectional_iterator_tag)
  		{
  			if(first != last)
  			{
  				BidirectionalIterator iCurrent, iNext, iLastModified;
  
  				last--;
  
  				while(first != last)
  				{
  					iLastModified = iNext = iCurrent = first;
  					
  					for(++iNext; iCurrent != last; iCurrent = iNext, ++iNext)
  					{
  						if(compare(*iNext, *iCurrent))
  						{
  							EASTL_VALIDATE_COMPARE(!compare(*iCurrent, *iNext)); // Validate that the compare function is sane.
  							iLastModified = iCurrent;
  							eastl::iter_swap(iCurrent, iNext);
  						}
  					}
  
  					last = iLastModified;
  				}
  			}
  		}
  	} // namespace Internal
  
  	template <typename ForwardIterator, typename StrictWeakOrdering>
  	inline void bubble_sort(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare)
  	{
  		typedef typename eastl::iterator_traits<ForwardIterator>::iterator_category IC;
  
  		eastl::Internal::bubble_sort_impl<ForwardIterator, StrictWeakOrdering>(first, last, compare, IC());
  	}
  
  	template <typename ForwardIterator>
  	inline void bubble_sort(ForwardIterator first, ForwardIterator last)
  	{
  		typedef eastl::less<typename eastl::iterator_traits<ForwardIterator>::value_type> Less;
  		typedef typename eastl::iterator_traits<ForwardIterator>::iterator_category IC;
  
  		eastl::Internal::bubble_sort_impl<ForwardIterator, Less>(first, last, Less(), IC());
  	}
  
  
  
  	/// sort
  	/// 
  	/// We use quick_sort by default. See quick_sort for details.
  	///
  	/// EASTL_DEFAULT_SORT_FUNCTION
  	/// If a default sort function is specified then call it, otherwise use EASTL's default quick_sort.
  	/// EASTL_DEFAULT_SORT_FUNCTION must be namespace-qualified and include any necessary template
  	/// parameters (e.g. eastl::comb_sort instead of just comb_sort), and it must be visible to this code. 
  	/// The EASTL_DEFAULT_SORT_FUNCTION must be provided in two versions: 
  	///     template <typename RandomAccessIterator>
  	///     void EASTL_DEFAULT_SORT_FUNCTION(RandomAccessIterator first, RandomAccessIterator last);
  	///
  	///     template <typename RandomAccessIterator, typename Compare>
  	///     void EASTL_DEFAULT_SORT_FUNCTION(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
  	///
  	template <typename RandomAccessIterator>
  	inline void sort(RandomAccessIterator first, RandomAccessIterator last)
  	{
  		#if defined(EASTL_DEFAULT_SORT_FUNCTION)
  			EASTL_DEFAULT_SORT_FUNCTION(first, last);
  		#else
  			eastl::quick_sort<RandomAccessIterator>(first, last);
  		#endif
  	}
  
  	template <typename RandomAccessIterator, typename Compare>
  	inline void sort(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
  	{
  		#if defined(EASTL_DEFAULT_SORT_FUNCTION)
  			EASTL_DEFAULT_SORT_FUNCTION(first, last, compare);
  		#else
  			eastl::quick_sort<RandomAccessIterator, Compare>(first, last, compare);
  		#endif
  	}
  
  
  
  	/// stable_sort
  	/// 
  	/// We use merge_sort by default. See merge_sort for details.
  	/// Beware that the used merge_sort -- and thus stable_sort -- allocates 
  	/// memory during execution. Try using merge_sort_buffer if you want
  	/// to avoid memory allocation.
  	///
  	/// EASTL_DEFAULT_STABLE_SORT_FUNCTION
  	/// If a default sort function is specified then call it, otherwise use EASTL's default merge_sort.
  	/// EASTL_DEFAULT_STABLE_SORT_FUNCTION must be namespace-qualified and include any necessary template
  	/// parameters (e.g. eastl::tim_sort instead of just tim_sort), and it must be visible to this code. 
  	/// The EASTL_DEFAULT_STABLE_SORT_FUNCTION must be provided in three versions, though the third
  	/// allocation implementation may choose to ignore the allocator parameter: 
  	///     template <typename RandomAccessIterator, typename StrictWeakOrdering>
  	///     void EASTL_DEFAULT_STABLE_SORT_FUNCTION(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering compare);
  	///     
  	///     template <typename RandomAccessIterator>
  	///     void EASTL_DEFAULT_STABLE_SORT_FUNCTION(RandomAccessIterator first, RandomAccessIterator last);
  	///
  	///     template <typename RandomAccessIterator, typename Allocator, typename StrictWeakOrdering>
  	///     void EASTL_DEFAULT_STABLE_SORT_FUNCTION(RandomAccessIterator first, RandomAccessIterator last, Allocator& allocator, StrictWeakOrdering compare);
  	///
  	template <typename RandomAccessIterator, typename StrictWeakOrdering>
  	void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering compare)
  	{
  		#if defined(EASTL_DEFAULT_STABLE_SORT_FUNCTION)
  			EASTL_DEFAULT_STABLE_SORT_FUNCTION(first, last, *get_default_allocator(0), compare);
  		#else
  			eastl::merge_sort<RandomAccessIterator, EASTLAllocatorType, StrictWeakOrdering>
  							 (first, last, *get_default_allocator(0), compare);
  		#endif
  	}
  
  	template <typename RandomAccessIterator>
  	void stable_sort(RandomAccessIterator first, RandomAccessIterator last)
  	{
  		#if defined(EASTL_DEFAULT_STABLE_SORT_FUNCTION)
  			EASTL_DEFAULT_STABLE_SORT_FUNCTION(first, last, *get_default_allocator(0));
  		#else
  			eastl::merge_sort<RandomAccessIterator, EASTLAllocatorType>
  							 (first, last, *get_default_allocator(0));
  		#endif
  	}
  
  	template <typename RandomAccessIterator, typename Allocator, typename StrictWeakOrdering>
  	void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Allocator& allocator, StrictWeakOrdering compare)
  	{
  		#if defined(EASTL_DEFAULT_STABLE_SORT_FUNCTION)
  			EASTL_DEFAULT_STABLE_SORT_FUNCTION(first, last, allocator, compare);
  		#else
  			eastl::merge_sort<RandomAccessIterator, Allocator, StrictWeakOrdering>(first, last, allocator, compare);
  		#endif
  	}
  
  	// This is not defined because it would cause compiler errors due to conflicts with a version above. 
  	//template <typename RandomAccessIterator, typename Allocator>
  	//void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Allocator& allocator)
  	//{
  	//    #if defined(EASTL_DEFAULT_STABLE_SORT_FUNCTION)
  	//        EASTL_DEFAULT_STABLE_SORT_FUNCTION<RandomAccessIterator, Allocator>(first, last, allocator);
  	//    #else
  	//        eastl::merge_sort<RandomAccessIterator, Allocator>(first, last, allocator);
  	//    #endif
  	//}
  
  
  
  
  	/* 
  	// Something to consider adding: An eastl sort which uses qsort underneath. 
  	// The primary purpose of this is to have an eastl interface for sorting which
  	// results in very little code generation, since all instances map to the 
  	// C qsort function.
  
  	template <typename T>
  	int small_footprint_sort_func(const void* a, const void* b)
  	{
  		if(*(const T*)a < *(const T*)b)
  			return -1;
  		if(*(const T*)a > *(const T*)b)
  			return +1;
  		return 0;
  	}
  
  	template <typename ContiguousIterator>
  	void small_footprint_sort(ContiguousIterator first, ContiguousIterator last)
  	{
  		typedef typename eastl::iterator_traits<ContiguousIterator>::value_type value_type;
  
  		qsort(first, (size_t)eastl::distance(first, last), sizeof(value_type), small_footprint_sort_func<value_type>);
  	}
  	*/
  
  } // namespace eastl
  
  
  #endif // Header include guard
  
  
  
  