openadk/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp

--- mozilla-release.orig/media/webrtc/trunk/webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp	2013-12-05 17:07:50.000000000 +0100
+++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp	2014-02-05 09:52:11.000000000 +0100
@@ -1,1688 +1,1694 @@
-//Templated spread_sort library
-
-//          Copyright Steven J. Ross 2001 - 2009.
-// Distributed under the Boost Software License, Version 1.0.
-//    (See accompanying file LICENSE_1_0.txt or copy at
-//          http://www.boost.org/LICENSE_1_0.txt)
-
-//  See http://www.boost.org/ for updates, documentation, and revision history.
-		  
-/*
-Some improvements suggested by:
-Phil Endecott and Frank Gennari
-Cygwin fix provided by:
-Scott McMurray
-*/
-
-#ifndef BOOST_SPREAD_SORT_H
-#define BOOST_SPREAD_SORT_H
-#include <algorithm>
-#include <cstring>
-#include <vector>
-#include "webrtc/system_wrappers/source/spreadsortlib/constants.hpp"
-
-namespace boost {
-  namespace detail {
-  	//This only works on unsigned data types
-  	template <typename T>
-  	inline unsigned 
-  	rough_log_2_size(const T& input) 
-  	{
-  		unsigned result = 0;
-  		//The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance
-  		while((input >> result) && (result < (8*sizeof(T)))) ++result;
-  		return result;
-  	}
-
-  	//Gets the maximum size which we'll call spread_sort on to control worst-case performance
-  	//Maintains both a minimum size to recurse and a check of distribution size versus count
-  	//This is called for a set of bins, instead of bin-by-bin, to avoid performance overhead
-  	inline size_t
-  	get_max_count(unsigned log_range, size_t count)
-  	{
-  		unsigned divisor = rough_log_2_size(count);
-  		//Making sure the divisor is positive
-  		if(divisor > LOG_MEAN_BIN_SIZE)
-  			divisor -= LOG_MEAN_BIN_SIZE;
-  		else
-  			divisor = 1;
-  		unsigned relative_width = (LOG_CONST * log_range)/((divisor > MAX_SPLITS) ? MAX_SPLITS : divisor);
-  		//Don't try to bitshift more than the size of an element
-  		if((8*sizeof(size_t)) <= relative_width)
-  			relative_width = (8*sizeof(size_t)) - 1;
-  		return (size_t)1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ? 
-  			(LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) :  relative_width);
-  	}
-
-  	//Find the minimum and maximum using <
-  	template <class RandomAccessIter>
-  	inline void 
-  	find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min)
-  	{
-  		min = max = current;
-  		//Start from the second item, as max and min are initialized to the first
-  		while(++current < last) {
-  			if(*max < *current)
-  				max = current;
-  			else if(*current < *min)
-  				min = current;
-  		}
-  	}
-
-  	//Uses a user-defined comparison operator to find minimum and maximum
-  	template <class RandomAccessIter, class compare>
-  	inline void 
-  	find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min, compare comp)
-  	{
-  		min = max = current;
-  		while(++current < last) {
-  			if(comp(*max, *current))
-  				max = current;
-  			else if(comp(*current, *min))
-  				min = current;
-  		}
-  	}
-
-  	//Gets a non-negative right bit shift to operate as a logarithmic divisor
-  	inline int
-  	get_log_divisor(size_t count, unsigned log_range)
-  	{
-  		int log_divisor;
-  		//If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so
-  		if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && log_range < MAX_SPLITS)
-  			log_divisor = 0;
-  		else {
-  			//otherwise divide the data into an optimized number of pieces
-  			log_divisor += LOG_MEAN_BIN_SIZE;
-  			if(log_divisor < 0)
-  				log_divisor = 0;
-  			//Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically
-  			if((log_range - log_divisor) > MAX_SPLITS)
-  				log_divisor = log_range - MAX_SPLITS;
-  		}
-  		return log_divisor;
-  	}
-
-  	template <class RandomAccessIter>
-  	inline RandomAccessIter * 
-  	size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
-  	{
-  		//Assure space for the size of each bin, followed by initializing sizes
-  		if(bin_count > bin_sizes.size())
-  			bin_sizes.resize(bin_count);
-  		for(size_t u = 0; u < bin_count; u++)
-  			bin_sizes[u] = 0;
-  		//Make sure there is space for the bins
-  		cache_end = cache_offset + bin_count;
-  		if(cache_end > bin_cache.size())
-  			bin_cache.resize(cache_end);
-  		return &(bin_cache[cache_offset]);
-  	}
-
-  	//Implementation for recursive integer sorting
-  	template <class RandomAccessIter, class div_type, class data_type>
-  	inline void 
-  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-  				  , std::vector<size_t> &bin_sizes)
-  	{
-  		//This step is roughly 10% of runtime, but it helps avoid worst-case behavior and improve behavior with real data
-  		//If you know the maximum and minimum ahead of time, you can pass those values in and skip this step for the first iteration
-  		RandomAccessIter max, min;
-  		find_extremes(first, last, max, min);
-  		//max and min will be the same (the first item) iff all values are equivalent
-  		if(max == min)
-  			return;
-  		RandomAccessIter * target_bin;
-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(*max >> 0) - (*min >> 0)));
-  		div_type div_min = *min >> log_divisor;
-  		div_type div_max = *max >> log_divisor;
-  		unsigned bin_count = div_max - div_min + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-  	
-  		//Calculating the size of each bin; this takes roughly 10% of runtime
-  		for (RandomAccessIter current = first; current != last;)
-  			bin_sizes[(*(current++) >> log_divisor) - div_min]++;
-  		//Assign the bin positions
-  		bins[0] = first;
-  		for(unsigned u = 0; u < bin_count - 1; u++)
-  			bins[u + 1] = bins[u] + bin_sizes[u];
-  
-  		//Swap into place
-  		//This dominates runtime, mostly in the swap and bin lookups
-  		RandomAccessIter nextbinstart = first;
-  		for(unsigned u = 0; u < bin_count - 1; ++u) {
-  			RandomAccessIter * local_bin = bins + u;
-  			nextbinstart += bin_sizes[u];
-  			//Iterating over each element in this bin
-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  				//Swapping elements in current into place until the correct element has been swapped in
-  				for(target_bin = (bins + ((*current >> log_divisor) - div_min));  target_bin != local_bin; 
-  					target_bin = bins + ((*current >> log_divisor) - div_min)) {
-  					//3-way swap; this is about 1% faster than a 2-way swap with integers
-  					//The main advantage is less copies are involved per item put in the correct place
-  					data_type tmp;
-  					RandomAccessIter b = (*target_bin)++;
-  					RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min);
-  					if (b_bin != local_bin) {
-  						RandomAccessIter c = (*b_bin)++;
-  						tmp = *c;
-  						*c = *b;
-  					} 
-  					else
-  						tmp = *b;
-  					*b = *current;
-  					*current = tmp;
-  				}
-  			}
-  			*local_bin = nextbinstart;
-  		}
-  		bins[bin_count - 1] = last;
-  
-  		//If we've bucketsorted, the array is sorted and we should skip recursion
-  		if(!log_divisor)
-  			return;
-  
-  		//Recursing; log_divisor is the remaining range
-  		size_t max_count = get_max_count(log_divisor, last - first);
-  		RandomAccessIter lastPos = first;
-  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			//don't sort unless there are at least two items to compare
-  			if(count < 2)
-  				continue;
-  			//using std::sort if its worst-case is better
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[u]);
-  			else
-  				spread_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
-  		}
-  	}
-
-  	//Generic bitshift-based 3-way swapping code
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-  	inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
-  		, const unsigned log_divisor, const div_type div_min) 
-  	{
-  		RandomAccessIter * local_bin = bins + ii;
-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  			for(RandomAccessIter * target_bin = (bins + (shift(*current, log_divisor) - div_min));  target_bin != local_bin; 
-  				target_bin = bins + (shift(*current, log_divisor) - div_min)) {
-  				data_type tmp;
-  				RandomAccessIter b = (*target_bin)++;
-  				RandomAccessIter * b_bin = bins + (shift(*b, log_divisor) - div_min);
-  				//Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
-  				if (b_bin != local_bin) {
-  					RandomAccessIter c = (*b_bin)++;
-  					tmp = *c;
-  					*c = *b;
-  				} 
-  				//Note: we could increment current once the swap is done in this case, but that seems to impair performance
-  				else
-  					tmp = *b;
-  				*b = *current;
-  				*current = tmp;
-  			}
-  		}
-  		*local_bin = nextbinstart;
-  	}
-
-  	//Standard swapping wrapper for ascending values
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-  	inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
-  		, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 
-  	{
-  		nextbinstart += bin_sizes[ii];
-  		inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, log_divisor, div_min);
-  	}
-
-  	//Functor implementation for recursive sorting
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-  	inline void 
-  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
-  	{
-  		RandomAccessIter max, min;
-  		find_extremes(first, last, max, min, comp);
-  		if(max == min)
-  			return;
-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
-  		div_type div_min = shift(*min, log_divisor);
-  		div_type div_max = shift(*max, log_divisor);
-  		unsigned bin_count = div_max - div_min + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-  			
-  		//Calculating the size of each bin
-  		for (RandomAccessIter current = first; current != last;)
-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-  		bins[0] = first;
-  		for(unsigned u = 0; u < bin_count - 1; u++)
-  			bins[u + 1] = bins[u] + bin_sizes[u];
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		for(unsigned u = 0; u < bin_count - 1; ++u)
-  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min);
-  		bins[bin_count - 1] = last;
-  		
-  		//If we've bucketsorted, the array is sorted and we should skip recursion
-  		if(!log_divisor)
-  			return;
-  		
-  		//Recursing
-  		size_t max_count = get_max_count(log_divisor, last - first);
-  		RandomAccessIter lastPos = first;
-  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[u], comp);
-  			else
-  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
-  		}
-  	}
-
-  	//Functor implementation for recursive sorting with only Shift overridden
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-  	inline void 
-  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-  					, std::vector<size_t> &bin_sizes, right_shift shift)
-  	{
-  		RandomAccessIter max, min;
-  		find_extremes(first, last, max, min);
-  		if(max == min)
-  			return;
-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
-  		div_type div_min = shift(*min, log_divisor);
-  		div_type div_max = shift(*max, log_divisor);
-  		unsigned bin_count = div_max - div_min + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-  			
-  		//Calculating the size of each bin
-  		for (RandomAccessIter current = first; current != last;)
-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-  		bins[0] = first;
-  		for(unsigned u = 0; u < bin_count - 1; u++)
-  			bins[u + 1] = bins[u] + bin_sizes[u];
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		for(unsigned ii = 0; ii < bin_count - 1; ++ii)
-  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
-  		bins[bin_count - 1] = last;
-  		
-  		//If we've bucketsorted, the array is sorted and we should skip recursion
-  		if(!log_divisor)
-  			return;
-  		
-  		//Recursing
-  		size_t max_count = get_max_count(log_divisor, last - first);
-  		RandomAccessIter lastPos = first;
-  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[u]);
-  			else
-  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
-  		}
-  	}
-
-  	//Holds the bin vector and makes the initial recursive call
-  	template <class RandomAccessIter, class div_type, class data_type>
-  	inline void 
-  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type)
-  	{
-  		std::vector<size_t> bin_sizes;
-  		std::vector<RandomAccessIter> bin_cache;
-  		spread_sort_rec<RandomAccessIter, div_type, data_type>(first, last, bin_cache, 0, bin_sizes);
-  	}
-
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-  	inline void 
-  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
-  	{
-  		std::vector<size_t> bin_sizes;
-  		std::vector<RandomAccessIter> bin_cache;
-  		spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp);
-  	}
-
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-  	inline void 
-  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
-  	{
-  		std::vector<size_t> bin_sizes;
-  		std::vector<RandomAccessIter> bin_cache;
-  		spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
-  	}
-  }
-
-  //Top-level sorting call for integers
-  template <class RandomAccessIter>
-  inline void integer_sort(RandomAccessIter first, RandomAccessIter last) 
-  {
-  	//Don't sort if it's too small to optimize
-  	if(last - first < detail::MIN_SORT_SIZE)
-  		std::sort(first, last);
-  	else
-  		detail::spread_sort(first, last, *first >> 0, *first);
-  }
-
-  //integer_sort with functors
-  template <class RandomAccessIter, class right_shift, class compare>
-  inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
-  						right_shift shift, compare comp) {
-  	if(last - first < detail::MIN_SORT_SIZE)
-  		std::sort(first, last, comp);
-  	else
-  		detail::spread_sort(first, last, shift(*first, 0), *first, shift, comp);
-  }
-
-  //integer_sort with right_shift functor
-  template <class RandomAccessIter, class right_shift>
-  inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
-  						right_shift shift) {
-  	if(last - first < detail::MIN_SORT_SIZE)
-  		std::sort(first, last);
-  	else
-  		detail::spread_sort(first, last, shift(*first, 0), *first, shift);
-  }
-
-  //------------------------------------------------------ float_sort source --------------------------------------
-  //Casts a RandomAccessIter to the specified data type
-  template<class cast_type, class RandomAccessIter>
-  inline cast_type
-  cast_float_iter(const RandomAccessIter & floatiter)
-  {
-  	cast_type result;
-  	std::memcpy(&result, &(*floatiter), sizeof(cast_type));
-  	return result;
-  }
-
-  //Casts a data element to the specified datinner_float_a type
-  template<class data_type, class cast_type>
-  inline cast_type
-  mem_cast(const data_type & data)
-  {
-  	cast_type result;
-  	std::memcpy(&result, &data, sizeof(cast_type));
-  	return result;
-  }
-
-  namespace detail {
-  	template <class RandomAccessIter, class div_type, class right_shift>
-  	inline void 
-  	find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift)
-  	{
-  		min = max = shift(*current, 0);
-  		while(++current < last) {
-  			div_type value = shift(*current, 0);
-  			if(max < value)
-  				max = value;
-  			else if(value < min)
-  				min = value;
-  		}
-  	}
-
-  	//Specialized swap loops for floating-point casting
-  	template <class RandomAccessIter, class div_type, class data_type>
-  	inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii
-  		, const unsigned log_divisor, const div_type div_min) 
-  	{
-  		RandomAccessIter * local_bin = bins + ii;
-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  			for(RandomAccessIter * target_bin = (bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min));  target_bin != local_bin; 
-  				target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) {
-  				data_type tmp;
-  				RandomAccessIter b = (*target_bin)++;
-  				RandomAccessIter * b_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(b) >> log_divisor) - div_min);
-  				//Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
-  				if (b_bin != local_bin) {
-  					RandomAccessIter c = (*b_bin)++;
-  					tmp = *c;
-  					*c = *b;
-  				} 
-  				else
-  					tmp = *b;
-  				*b = *current;
-  				*current = tmp;
-  			}
-  		}
-  		*local_bin = nextbinstart;
-  	}
-
-  	template <class RandomAccessIter, class div_type, class data_type>
-  	inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii
-  		, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 
-  	{
-  		nextbinstart += bin_sizes[ii];
-  		inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, log_divisor, div_min);
-  	}
-
-  	template <class RandomAccessIter, class cast_type>
-  	inline void 
-  	find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min)
-  	{
-  		min = max = cast_float_iter<cast_type, RandomAccessIter>(current);
-  		while(++current < last) {
-  			cast_type value = cast_float_iter<cast_type, RandomAccessIter>(current);
-  			if(max < value)
-  				max = value;
-  			else if(value < min)
-  				min = value;
-  		}
-  	}
-
-  	//Special-case sorting of positive floats with casting instead of a right_shift
-  	template <class RandomAccessIter, class div_type, class data_type>
-  	inline void 
-  	positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-  					, std::vector<size_t> &bin_sizes)
-  	{
-  		div_type max, min;
-  		find_extremes(first, last, max, min);
-  		if(max == min)
-  			return;
-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-  		div_type div_min = min >> log_divisor;
-  		div_type div_max = max >> log_divisor;
-  		unsigned bin_count = div_max - div_min + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-  			
-  		//Calculating the size of each bin
-  		for (RandomAccessIter current = first; current != last;)
-  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
-  		bins[0] = first;
-  		for(unsigned u = 0; u < bin_count - 1; u++)
-  			bins[u + 1] = bins[u] + bin_sizes[u];
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		for(unsigned u = 0; u < bin_count - 1; ++u)
-  			float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, bin_sizes, log_divisor, div_min);
-  		bins[bin_count - 1] = last;
-  		
-  		//Return if we've completed bucketsorting
-  		if(!log_divisor)
-  			return;
-  		
-  		//Recursing
-  		size_t max_count = get_max_count(log_divisor, last - first);
-  		RandomAccessIter lastPos = first;
-  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[u]);
-  			else
-  				positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
-  		}
-  	}
-
-  	//Sorting negative_ float_s
-  	//Note that bins are iterated in reverse order because max_neg_float = min_neg_int
-  	template <class RandomAccessIter, class div_type, class data_type>
-  	inline void 
-  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-  					, std::vector<size_t> &bin_sizes)
-  	{
-  		div_type max, min;
-  		find_extremes(first, last, max, min);
-  		if(max == min)
-  			return;
-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-  		div_type div_min = min >> log_divisor;
-  		div_type div_max = max >> log_divisor;
-  		unsigned bin_count = div_max - div_min + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-  			
-  		//Calculating the size of each bin
-  		for (RandomAccessIter current = first; current != last;)
-  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
-  		bins[bin_count - 1] = first;
-  		for(int ii = bin_count - 2; ii >= 0; --ii)
-  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		//The last bin will always have the correct elements in it
-  		for(int ii = bin_count - 1; ii > 0; --ii)
-  			float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);
-  		//Since we don't process the last bin, we need to update its end position
-  		bin_cache[cache_offset] = last;
-  		
-  		//Return if we've completed bucketsorting
-  		if(!log_divisor)
-  			return;
-  		
-  		//Recursing
-  		size_t max_count = get_max_count(log_divisor, last - first);
-  		RandomAccessIter lastPos = first;
-  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
-  			size_t count = bin_cache[ii] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[ii]);
-  			else
-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
-  		}
-  	}
-
-  	//Sorting negative_ float_s
-  	//Note that bins are iterated in reverse order because max_neg_float = min_neg_int
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-  	inline void 
-  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-  					, std::vector<size_t> &bin_sizes, right_shift shift)
-  	{
-  		div_type max, min;
-  		find_extremes(first, last, max, min, shift);
-  		if(max == min)
-  			return;
-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-  		div_type div_min = min >> log_divisor;
-  		div_type div_max = max >> log_divisor;
-  		unsigned bin_count = div_max - div_min + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-  			
-  		//Calculating the size of each bin
-  		for (RandomAccessIter current = first; current != last;)
-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-  		bins[bin_count - 1] = first;
-  		for(int ii = bin_count - 2; ii >= 0; --ii)
-  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		//The last bin will always have the correct elements in it
-  		for(int ii = bin_count - 1; ii > 0; --ii)
-  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
-  		//Since we don't process the last bin, we need to update its end position
-  		bin_cache[cache_offset] = last;
-  		
-  		//Return if we've completed bucketsorting
-  		if(!log_divisor)
-  			return;
-  		
-  		//Recursing
-  		size_t max_count = get_max_count(log_divisor, last - first);
-  		RandomAccessIter lastPos = first;
-  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
-  			size_t count = bin_cache[ii] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[ii]);
-  			else
-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
-  		}
-  	}
-
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-  	inline void 
-  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
-  	{
-  		div_type max, min;
-  		find_extremes(first, last, max, min, shift);
-  		if(max == min)
-  			return;
-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-  		div_type div_min = min >> log_divisor;
-  		div_type div_max = max >> log_divisor;
-  		unsigned bin_count = div_max - div_min + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-  			
-  		//Calculating the size of each bin
-  		for (RandomAccessIter current = first; current != last;)
-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-  		bins[bin_count - 1] = first;
-  		for(int ii = bin_count - 2; ii >= 0; --ii)
-  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		//The last bin will always have the correct elements in it
-  		for(int ii = bin_count - 1; ii > 0; --ii)
-  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
-  		//Since we don't process the last bin, we need to update its end position
-  		bin_cache[cache_offset] = last;
-  		
-  		//Return if we've completed bucketsorting
-  		if(!log_divisor)
-  			return;
-  		
-  		//Recursing
-  		size_t max_count = get_max_count(log_divisor, last - first);
-  		RandomAccessIter lastPos = first;
-  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
-  			size_t count = bin_cache[ii] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[ii], comp);
-  			else
-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
-  		}
-  	}
-
-  	//Casting special-case for floating-point sorting
-  	template <class RandomAccessIter, class div_type, class data_type>
-  	inline void 
-  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-  					, std::vector<size_t> &bin_sizes)
-  	{
-  		div_type max, min;
-  		find_extremes(first, last, max, min);
-  		if(max == min)
-  			return;
-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-  		div_type div_min = min >> log_divisor;
-  		div_type div_max = max >> log_divisor;
-  		unsigned bin_count = div_max - div_min + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-  			
-  		//Calculating the size of each bin
-  		for (RandomAccessIter current = first; current != last;)
-  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
-  		//The index of the first positive bin
-  		div_type first_positive = (div_min < 0) ? -div_min : 0;
-  		//Resetting if all bins are negative
-  		if(cache_offset + first_positive > cache_end)
-  			first_positive = cache_end - cache_offset;
-  		//Reversing the order of the negative bins
-  		//Note that because of the negative/positive ordering direction flip
-  		//We can not depend upon bin order and positions matching up
-  		//so bin_sizes must be reused to contain the end of the bin
-  		if(first_positive > 0) {
-  			bins[first_positive - 1] = first;
-  			for(int ii = first_positive - 2; ii >= 0; --ii) {
-  				bins[ii] = first + bin_sizes[ii + 1];
-  				bin_sizes[ii] += bin_sizes[ii + 1];
-  			}
-  			//Handling positives following negatives
-  			if((unsigned)first_positive < bin_count) {
-  				bins[first_positive] = first + bin_sizes[0];
-  				bin_sizes[first_positive] += bin_sizes[0];
-  			}
-  		}
-  		else
-  			bins[0] = first;
-  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
-  			bins[u + 1] = first + bin_sizes[u];
-  			bin_sizes[u + 1] += bin_sizes[u];
-  		}
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		for(unsigned u = 0; u < bin_count; ++u) {
-  			nextbinstart = first + bin_sizes[u];
-  			inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, log_divisor, div_min);
-  		}
-  		
-  		if(!log_divisor)
-  			return;
-  		
-  		//Handling negative values first
-  		size_t max_count = get_max_count(log_divisor, last - first);
-  		RandomAccessIter lastPos = first;
-  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
-  			size_t count = bin_cache[ii] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[ii]);
-  			//sort negative values using reversed-bin spread_sort
-  			else
-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
-  		}
-  		
-  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[u]);
-  			//sort positive values using normal spread_sort
-  			else
-  				positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
-  		}
-  	}
-
-  	//Functor implementation for recursive sorting
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-  	inline void 
-  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-  					, std::vector<size_t> &bin_sizes, right_shift shift)
-  	{
-  		div_type max, min;
-  		find_extremes(first, last, max, min, shift);
-  		if(max == min)
-  			return;
-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-  		div_type div_min = min >> log_divisor;
-  		div_type div_max = max >> log_divisor;
-  		unsigned bin_count = div_max - div_min + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-  			
-  		//Calculating the size of each bin
-  		for (RandomAccessIter current = first; current != last;)
-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-  		//The index of the first positive bin
-  		div_type first_positive = (div_min < 0) ? -div_min : 0;
-  		//Resetting if all bins are negative
-  		if(cache_offset + first_positive > cache_end)
-  			first_positive = cache_end - cache_offset;
-  		//Reversing the order of the negative bins
-  		//Note that because of the negative/positive ordering direction flip
-  		//We can not depend upon bin order and positions matching up
-  		//so bin_sizes must be reused to contain the end of the bin
-  		if(first_positive > 0) {
-  			bins[first_positive - 1] = first;
-  			for(int ii = first_positive - 2; ii >= 0; --ii) {
-  				bins[ii] = first + bin_sizes[ii + 1];
-  				bin_sizes[ii] += bin_sizes[ii + 1];
-  			}
-  			//Handling positives following negatives
-  			if((unsigned)first_positive < bin_count) {
-  				bins[first_positive] = first + bin_sizes[0];
-  				bin_sizes[first_positive] += bin_sizes[0];
-  			}
-  		}
-  		else
-  			bins[0] = first;
-  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
-  			bins[u + 1] = first + bin_sizes[u];
-  			bin_sizes[u + 1] += bin_sizes[u];
-  		}
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		for(unsigned u = 0; u < bin_count; ++u) {
-  			nextbinstart = first + bin_sizes[u];
-  			inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
-  		}
-  		
-  		//Return if we've completed bucketsorting
-  		if(!log_divisor)
-  			return;
-  		
-  		//Handling negative values first
-  		size_t max_count = get_max_count(log_divisor, last - first);
-  		RandomAccessIter lastPos = first;
-  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
-  			size_t count = bin_cache[ii] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[ii]);
-  			//sort negative values using reversed-bin spread_sort
-  			else
-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
-  		}
-  		
-  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[u]);
-  			//sort positive values using normal spread_sort
-  			else
-  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
-  		}
-  	}
-
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-  	inline void 
-  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
-  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
-  	{
-  		div_type max, min;
-  		find_extremes(first, last, max, min, shift);
-  		if(max == min)
-  			return;
-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
-  		div_type div_min = min >> log_divisor;
-  		div_type div_max = max >> log_divisor;
-  		unsigned bin_count = div_max - div_min + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
-  			
-  		//Calculating the size of each bin
-  		for (RandomAccessIter current = first; current != last;)
-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
-  		//The index of the first positive bin
-  		div_type first_positive = (div_min < 0) ? -div_min : 0;
-  		//Resetting if all bins are negative
-  		if(cache_offset + first_positive > cache_end)
-  			first_positive = cache_end - cache_offset;
-  		//Reversing the order of the negative bins
-  		//Note that because of the negative/positive ordering direction flip
-  		//We can not depend upon bin order and positions matching up
-  		//so bin_sizes must be reused to contain the end of the bin
-  		if(first_positive > 0) {
-  			bins[first_positive - 1] = first;
-  			for(int ii = first_positive - 2; ii >= 0; --ii) {
-  				bins[ii] = first + bin_sizes[ii + 1];
-  				bin_sizes[ii] += bin_sizes[ii + 1];
-  			}
-  			//Handling positives following negatives
-  			if((unsigned)first_positive < bin_count) {
-  				bins[first_positive] = first + bin_sizes[0];
-  				bin_sizes[first_positive] += bin_sizes[0];
-  			}
-  		}
-  		else
-  			bins[0] = first;
-  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
-  			bins[u + 1] = first + bin_sizes[u];
-  			bin_sizes[u + 1] += bin_sizes[u];
-  		}
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		for(unsigned u = 0; u < bin_count; ++u) {
-  			nextbinstart = first + bin_sizes[u];
-  			inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
-  		}
-  		
-  		//Return if we've completed bucketsorting
-  		if(!log_divisor)
-  			return;
-  		
-  		//Handling negative values first
-  		size_t max_count = get_max_count(log_divisor, last - first);
-  		RandomAccessIter lastPos = first;
-  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
-  			size_t count = bin_cache[ii] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[ii]);
-  			//sort negative values using reversed-bin spread_sort
-  			else
-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
-  		}
-  		
-  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			if(count < 2)
-  				continue;
-  			if(count < max_count)
-  				std::sort(lastPos, bin_cache[u]);
-  			//sort positive values using normal spread_sort
-  			else
-  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
-  		}
-  	}
-
-  	template <class RandomAccessIter, class cast_type, class data_type>
-  	inline void 
-  	float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, data_type)
-  	{
-  		std::vector<size_t> bin_sizes;
-  		std::vector<RandomAccessIter> bin_cache;
-  		float_sort_rec<RandomAccessIter, cast_type, data_type>(first, last, bin_cache, 0, bin_sizes);
-  	}
-
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
-  	inline void 
-  	float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
-  	{
-  		std::vector<size_t> bin_sizes;
-  		std::vector<RandomAccessIter> bin_cache;
-  		float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
-  	}
-
-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
-  	inline void 
-  	float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
-  	{
-  		std::vector<size_t> bin_sizes;
-  		std::vector<RandomAccessIter> bin_cache;
-  		float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift, comp);
-  	}
-  }
-
-  //float_sort with casting
-  //The cast_type must be equal in size to the data type, and must be a signed integer
-  template <class RandomAccessIter, class cast_type>
-  inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cast_type cVal) 
-  {
-  	if(last - first < detail::MIN_SORT_SIZE)
-  		std::sort(first, last);
-  	else
-  		detail::float_Sort(first, last, cVal, *first);
-  }
-
-  //float_sort with casting to an int
-  //Only use this with IEEE floating-point numbers
-  template <class RandomAccessIter>
-  inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter last) 
-  {
-  	int cVal = 0;
-  	float_sort_cast(first, last, cVal);
-  }
-
-  //float_sort with functors
-  template <class RandomAccessIter, class right_shift>
-  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift) 
-  {
-  	if(last - first < detail::MIN_SORT_SIZE)
-  		std::sort(first, last);
-  	else
-  		detail::float_Sort(first, last, shift(*first, 0), *first, shift);
-  }
-
-  template <class RandomAccessIter, class right_shift, class compare>
-  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift, compare comp) 
-  {
-  	if(last - first < detail::MIN_SORT_SIZE)
-  		std::sort(first, last, comp);
-  	else
-  		detail::float_Sort(first, last, shift(*first, 0), *first, shift, comp);
-  }
-
-  //------------------------------------------------- string_sort source ---------------------------------------------
-  namespace detail {
-  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.
-  	template<class RandomAccessIter>
-  	inline void
-  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset)
-  	{
-  		unsigned nextOffset = char_offset;
-  		bool done = false;
-  		while(!done) {
-  			RandomAccessIter curr = first;
-  			do {
-  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
-  				if((*curr).size() > char_offset && ((*curr).size() <= (nextOffset + 1) || (*curr)[nextOffset] != (*first)[nextOffset])) {
-  					done = true;
-  					break;
-  				}
-  			} while(++curr != finish);
-  			if(!done)
-  				++nextOffset;
-  		} 
-  		char_offset = nextOffset;
-  	}
-
-  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.
-  	template<class RandomAccessIter, class get_char, class get_length>
-  	inline void
-  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length)
-  	{
-  		unsigned nextOffset = char_offset;
-  		bool done = false;
-  		while(!done) {
-  			RandomAccessIter curr = first;
-  			do {
-  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
-  				if(length(*curr) > char_offset && (length(*curr) <= (nextOffset + 1) || getchar((*curr), nextOffset) != getchar((*first), nextOffset))) {
-  					done = true;
-  					break;
-  				}
-  			} while(++curr != finish);
-  			if(!done)
-  				++nextOffset;
-  		} 
-  		char_offset = nextOffset;
-  	}
-
-  	//A comparison functor for strings that assumes they are identical up to char_offset
-  	template<class data_type, class unsignedchar_type>
-  	struct offset_lessthan {
-  		offset_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
-  		inline bool operator()(const data_type &x, const data_type &y) const 
-  		{
-  			unsigned minSize = std::min(x.size(), y.size());
-  			for(unsigned u = fchar_offset; u < minSize; ++u) {
-  				if(static_cast<unsignedchar_type>(x[u]) < static_cast<unsignedchar_type>(y[u]))
-  					return true;
-  				else if(static_cast<unsignedchar_type>(y[u]) < static_cast<unsignedchar_type>(x[u]))
-  					return false;
-  			}
-  			return x.size() < y.size();
-  		}
-  		unsigned fchar_offset;
-  	};
-
-  	//A comparison functor for strings that assumes they are identical up to char_offset
-  	template<class data_type, class unsignedchar_type>
-  	struct offset_greaterthan {
-  		offset_greaterthan(unsigned char_offset) : fchar_offset(char_offset){}
-  		inline bool operator()(const data_type &x, const data_type &y) const 
-  		{
-  			unsigned minSize = std::min(x.size(), y.size());
-  			for(unsigned u = fchar_offset; u < minSize; ++u) {
-  				if(static_cast<unsignedchar_type>(x[u]) > static_cast<unsignedchar_type>(y[u]))
-  					return true;
-  				else if(static_cast<unsignedchar_type>(y[u]) > static_cast<unsignedchar_type>(x[u]))
-  					return false;
-  			}
-  			return x.size() > y.size();
-  		}
-  		unsigned fchar_offset;
-  	};
-
-  	//A comparison functor for strings that assumes they are identical up to char_offset
-  	template<class data_type, class get_char, class get_length>
-  	struct offset_char_lessthan {
-  		offset_char_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
-  		inline bool operator()(const data_type &x, const data_type &y) const 
-  		{
-  			unsigned minSize = std::min(length(x), length(y));
-  			for(unsigned u = fchar_offset; u < minSize; ++u) {
-  				if(getchar(x, u) < getchar(y, u))
-  					return true;
-  				else if(getchar(y, u) < getchar(x, u))
-  					return false;
-  			}
-  			return length(x) < length(y);
-  		}
-  		unsigned fchar_offset;
-  		get_char getchar;
-  		get_length length;
-  	};
-
-  	//String sorting recursive implementation
-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
-  	inline void 
-  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)
-  	{
-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-  		//Iterate to the end of the empties.  If all empty, return
-  		while((*first).size() <= char_offset) {
-  			if(++first == last)
-  				return;
-  		}
-  		RandomAccessIter finish = last - 1;
-  		//Getting the last non-empty
-  		for(;(*finish).size() <= char_offset; --finish) { }
-  		++finish;
-  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
-  		update_offset(first, finish, char_offset);
-  		
-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-  		const unsigned max_size = bin_count;
-  		const unsigned membin_count = bin_count + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
-  			
-  		//Calculating the size of each bin; this takes roughly 10% of runtime
-  		for (RandomAccessIter current = first; current != last; ++current) {
-  			if((*current).size() <= char_offset) {
-  				bin_sizes[0]++;
-  			}
-  			else
-  				bin_sizes[static_cast<unsignedchar_type>((*current)[char_offset]) + 1]++;
-  		}
-  		//Assign the bin positions
-  		bin_cache[cache_offset] = first;
-  		for(unsigned u = 0; u < membin_count - 1; u++)
-  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		//handling empty bins
-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
-  		nextbinstart +=	bin_sizes[0];
-  		RandomAccessIter * target_bin;
-  		//Iterating over each element in the bin of empties
-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  			//empties belong in this bin
-  			while((*current).size() > char_offset) {
-  				target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);
-  				iter_swap(current, (*target_bin)++);
-  			}
-  		}
-  		*local_bin = nextbinstart;
-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-  		unsigned last_bin = bin_count - 1;
-  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
-  		//This dominates runtime, mostly in the swap and bin lookups
-  		for(unsigned u = 0; u < last_bin; ++u) {
-  			local_bin = bins + u;
-  			nextbinstart += bin_sizes[u + 1];
-  			//Iterating over each element in this bin
-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  				//Swapping elements in current into place until the correct element has been swapped in
-  				for(target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 
-  					target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]))
-  					iter_swap(current, (*target_bin)++);
-  			}
-  			*local_bin = nextbinstart;
-  		}
-  		bins[last_bin] = last;
-  		//Recursing
-  		RandomAccessIter lastPos = bin_cache[cache_offset];
-  		//Skip this loop for empties
-  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			//don't sort unless there are at least two items to compare
-  			if(count < 2)
-  				continue;
-  			//using std::sort if its worst-case is better
-  			if(count < max_size)
-  				std::sort(lastPos, bin_cache[u], offset_lessthan<data_type, unsignedchar_type>(char_offset + 1));
-  			else
-  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
-  		}
-  	}
-
-  	//Sorts strings in reverse order, with empties at the end
-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
-  	inline void 
-  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)
-  	{
-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-  		RandomAccessIter curr = first;
-  		//Iterate to the end of the empties.  If all empty, return
-  		while((*curr).size() <= char_offset) {
-  			if(++curr == last)
-  				return;
-  		}
-  		//Getting the last non-empty
-  		while((*(--last)).size() <= char_offset) { }
-  		++last;
-  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
-  		update_offset(curr, last, char_offset);
-  		RandomAccessIter * target_bin;
-  		
-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-  		const unsigned max_size = bin_count;
-  		const unsigned membin_count = bin_count + 1;
-  		const unsigned max_bin = bin_count - 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
-  		RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin]);
-  			
-  		//Calculating the size of each bin; this takes roughly 10% of runtime
-  		for (RandomAccessIter current = first; current != last; ++current) {
-  			if((*current).size() <= char_offset) {
-  				bin_sizes[bin_count]++;
-  			}
-  			else
-  				bin_sizes[max_bin - static_cast<unsignedchar_type>((*current)[char_offset])]++;
-  		}
-  		//Assign the bin positions
-  		bin_cache[cache_offset] = first;
-  		for(unsigned u = 0; u < membin_count - 1; u++)
-  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = last;
-  		//handling empty bins
-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
-  		RandomAccessIter lastFull = *local_bin;
-  		//Iterating over each element in the bin of empties
-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  			//empties belong in this bin
-  			while((*current).size() > char_offset) {
-  				target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);
-  				iter_swap(current, (*target_bin)++);
-  			}
-  		}
-  		*local_bin = nextbinstart;
-  		nextbinstart = first;
-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-  		unsigned last_bin = max_bin;
-  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
-  		//This dominates runtime, mostly in the swap and bin lookups
-  		for(unsigned u = 0; u < last_bin; ++u) {
-  			local_bin = bins + u;
-  			nextbinstart += bin_sizes[u];
-  			//Iterating over each element in this bin
-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  				//Swapping elements in current into place until the correct element has been swapped in
-  				for(target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 
-  					target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]))
-  					iter_swap(current, (*target_bin)++);
-  			}
-  			*local_bin = nextbinstart;
-  		}
-  		bins[last_bin] = lastFull;
-  		//Recursing
-  		RandomAccessIter lastPos = first;
-  		//Skip this loop for empties
-  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			//don't sort unless there are at least two items to compare
-  			if(count < 2)
-  				continue;
-  			//using std::sort if its worst-case is better
-  			if(count < max_size)
-  				std::sort(lastPos, bin_cache[u], offset_greaterthan<data_type, unsignedchar_type>(char_offset + 1));
-  			else
-  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
-  		}
-  	}
-
-  	//String sorting recursive implementation
-  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length>
-  	inline void 
-  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length)
-  	{
-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-  		//Iterate to the end of the empties.  If all empty, return
-  		while(length(*first) <= char_offset) {
-  			if(++first == last)
-  				return;
-  		}
-  		RandomAccessIter finish = last - 1;
-  		//Getting the last non-empty
-  		for(;length(*finish) <= char_offset; --finish) { }
-  		++finish;
-  		update_offset(first, finish, char_offset, getchar, length);
-  		
-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-  		const unsigned max_size = bin_count;
-  		const unsigned membin_count = bin_count + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
-  			
-  		//Calculating the size of each bin; this takes roughly 10% of runtime
-  		for (RandomAccessIter current = first; current != last; ++current) {
-  			if(length(*current) <= char_offset) {
-  				bin_sizes[0]++;
-  			}
-  			else
-  				bin_sizes[getchar((*current), char_offset) + 1]++;
-  		}
-  		//Assign the bin positions
-  		bin_cache[cache_offset] = first;
-  		for(unsigned u = 0; u < membin_count - 1; u++)
-  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		//handling empty bins
-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
-  		nextbinstart +=	bin_sizes[0];
-  		RandomAccessIter * target_bin;
-  		//Iterating over each element in the bin of empties
-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  			//empties belong in this bin
-  			while(length(*current) > char_offset) {
-  				target_bin = bins + getchar((*current), char_offset);
-  				iter_swap(current, (*target_bin)++);
-  			}
-  		}
-  		*local_bin = nextbinstart;
-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-  		unsigned last_bin = bin_count - 1;
-  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
-  		//This dominates runtime, mostly in the swap and bin lookups
-  		for(unsigned ii = 0; ii < last_bin; ++ii) {
-  			local_bin = bins + ii;
-  			nextbinstart += bin_sizes[ii + 1];
-  			//Iterating over each element in this bin
-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  				//Swapping elements in current into place until the correct element has been swapped in
-  				for(target_bin = bins + getchar((*current), char_offset);  target_bin != local_bin; 
-  					target_bin = bins + getchar((*current), char_offset))
-  					iter_swap(current, (*target_bin)++);
-  			}
-  			*local_bin = nextbinstart;
-  		}
-  		bins[last_bin] = last;
-  		
-  		//Recursing
-  		RandomAccessIter lastPos = bin_cache[cache_offset];
-  		//Skip this loop for empties
-  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			//don't sort unless there are at least two items to compare
-  			if(count < 2)
-  				continue;
-  			//using std::sort if its worst-case is better
-  			if(count < max_size)
-  				std::sort(lastPos, bin_cache[u], offset_char_lessthan<data_type, get_char, get_length>(char_offset + 1));
-  			else
-  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length);
-  		}
-  	}
-
-  	//String sorting recursive implementation
-  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
-  	inline void 
-  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
-  	{
-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-  		//Iterate to the end of the empties.  If all empty, return
-  		while(length(*first) <= char_offset) {
-  			if(++first == last)
-  				return;
-  		}
-  		RandomAccessIter finish = last - 1;
-  		//Getting the last non-empty
-  		for(;length(*finish) <= char_offset; --finish) { }
-  		++finish;
-  		update_offset(first, finish, char_offset, getchar, length);
-  		
-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-  		const unsigned max_size = bin_count;
-  		const unsigned membin_count = bin_count + 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
-  			
-  		//Calculating the size of each bin; this takes roughly 10% of runtime
-  		for (RandomAccessIter current = first; current != last; ++current) {
-  			if(length(*current) <= char_offset) {
-  				bin_sizes[0]++;
-  			}
-  			else
-  				bin_sizes[getchar((*current), char_offset) + 1]++;
-  		}
-  		//Assign the bin positions
-  		bin_cache[cache_offset] = first;
-  		for(unsigned u = 0; u < membin_count - 1; u++)
-  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = first;
-  		//handling empty bins
-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
-  		nextbinstart +=	bin_sizes[0];
-  		RandomAccessIter * target_bin;
-  		//Iterating over each element in the bin of empties
-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  			//empties belong in this bin
-  			while(length(*current) > char_offset) {
-  				target_bin = bins + getchar((*current), char_offset);
-  				iter_swap(current, (*target_bin)++);
-  			}
-  		}
-  		*local_bin = nextbinstart;
-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-  		unsigned last_bin = bin_count - 1;
-  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
-  		//This dominates runtime, mostly in the swap and bin lookups
-  		for(unsigned u = 0; u < last_bin; ++u) {
-  			local_bin = bins + u;
-  			nextbinstart += bin_sizes[u + 1];
-  			//Iterating over each element in this bin
-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  				//Swapping elements in current into place until the correct element has been swapped in
-  				for(target_bin = bins + getchar((*current), char_offset);  target_bin != local_bin; 
-  					target_bin = bins + getchar((*current), char_offset))
-  					iter_swap(current, (*target_bin)++);
-  			}
-  			*local_bin = nextbinstart;
-  		}
-  		bins[last_bin] = last;
-  		
-  		//Recursing
-  		RandomAccessIter lastPos = bin_cache[cache_offset];
-  		//Skip this loop for empties
-  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			//don't sort unless there are at least two items to compare
-  			if(count < 2)
-  				continue;
-  			//using std::sort if its worst-case is better
-  			if(count < max_size)
-  				std::sort(lastPos, bin_cache[u], comp);
-  			else
-  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
-  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
-  		}
-  	}
-
-  	//Sorts strings in reverse order, with empties at the end
-  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
-  	inline void 
-  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
-  	{
-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
-  		RandomAccessIter curr = first;
-  		//Iterate to the end of the empties.  If all empty, return
-  		while(length(*curr) <= char_offset) {
-  			if(++curr == last)
-  				return;
-  		}
-  		//Getting the last non-empty
-  		while(length(*(--last)) <= char_offset) { }
-  		++last;
-  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
-  		update_offset(first, last, char_offset, getchar, length);
-  		
-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
-  		const unsigned max_size = bin_count;
-  		const unsigned membin_count = bin_count + 1;
-  		const unsigned max_bin = bin_count - 1;
-  		unsigned cache_end;
-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
-  		RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]);
-  			
-  		//Calculating the size of each bin; this takes roughly 10% of runtime
-  		for (RandomAccessIter current = first; current != last; ++current) {
-  			if(length(*current) <= char_offset) {
-  				bin_sizes[bin_count]++;
-  			}
-  			else
-  				bin_sizes[max_bin - getchar((*current), char_offset)]++;
-  		}
-  		//Assign the bin positions
-  		bin_cache[cache_offset] = first;
-  		for(unsigned u = 0; u < membin_count - 1; u++)
-  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
-  		
-  		//Swap into place
-  		RandomAccessIter nextbinstart = last;
-  		//handling empty bins
-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
-  		RandomAccessIter lastFull = *local_bin;
-  		RandomAccessIter * target_bin;
-  		//Iterating over each element in the bin of empties
-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  			//empties belong in this bin
-  			while(length(*current) > char_offset) {
-  				target_bin = end_bin - getchar((*current), char_offset);
-  				iter_swap(current, (*target_bin)++);
-  			}
-  		}
-  		*local_bin = nextbinstart;
-  		nextbinstart = first;
-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
-  		unsigned last_bin = max_bin;
-  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
-  		//This dominates runtime, mostly in the swap and bin lookups
-  		for(unsigned u = 0; u < last_bin; ++u) {
-  			local_bin = bins + u;
-  			nextbinstart += bin_sizes[u];
-  			//Iterating over each element in this bin
-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
-  				//Swapping elements in current into place until the correct element has been swapped in
-  				for(target_bin = end_bin - getchar((*current), char_offset);  target_bin != local_bin; 
-  					target_bin = end_bin - getchar((*current), char_offset))
-  					iter_swap(current, (*target_bin)++);
-  			}
-  			*local_bin = nextbinstart;
-  		}
-  		bins[last_bin] = lastFull;
-  		//Recursing
-  		RandomAccessIter lastPos = first;
-  		//Skip this loop for empties
-  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
-  			size_t count = bin_cache[u] - lastPos;
-  			//don't sort unless there are at least two items to compare
-  			if(count < 2)
-  				continue;
-  			//using std::sort if its worst-case is better
-  			if(count < max_size)
-  				std::sort(lastPos, bin_cache[u], comp);
-  			else
-  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
-  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
-  		}
-  	}
-
-  	//Holds the bin vector and makes the initial recursive call
-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
-  	inline void 
-  	string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
-  	{
-  		std::vector<size_t> bin_sizes;
-  		std::vector<RandomAccessIter> bin_cache;
-  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
-  	}
-
-  	//Holds the bin vector and makes the initial recursive call
-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
-  	inline void 
-  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
-  	{
-  		std::vector<size_t> bin_sizes;
-  		std::vector<RandomAccessIter> bin_cache;
-  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
-  	}
-
-  	//Holds the bin vector and makes the initial recursive call
-  	template <class RandomAccessIter, class get_char, class get_length, class data_type, class unsignedchar_type>
-  	inline void 
-  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, data_type, unsignedchar_type)
-  	{
-  		std::vector<size_t> bin_sizes;
-  		std::vector<RandomAccessIter> bin_cache;
-  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length);
-  	}
-
-  	//Holds the bin vector and makes the initial recursive call
-  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
-  	inline void 
-  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
-  	{
-  		std::vector<size_t> bin_sizes;
-  		std::vector<RandomAccessIter> bin_cache;
-  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
-  	}
-
-  	//Holds the bin vector and makes the initial recursive call
-  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
-  	inline void 
-  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
-  	{
-  		std::vector<size_t> bin_sizes;
-  		std::vector<RandomAccessIter> bin_cache;
-  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
-  	}
-  }
-
-  //Allows character-type overloads
-  template <class RandomAccessIter, class unsignedchar_type>
-  inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsignedchar_type unused) 
-  {
-  	//Don't sort if it's too small to optimize
-  	if(last - first < detail::MIN_SORT_SIZE)
-  		std::sort(first, last);
-  	else
-  		detail::string_sort(first, last, *first, unused);
-  }
-
-  //Top-level sorting call; wraps using default of unsigned char
-  template <class RandomAccessIter>
-  inline void string_sort(RandomAccessIter first, RandomAccessIter last) 
-  {
-  	unsigned char unused = '\0';
-  	string_sort(first, last, unused);
-  }
-
-  //Allows character-type overloads
-  template <class RandomAccessIter, class compare, class unsignedchar_type>
-  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused) 
-  {
-  	//Don't sort if it's too small to optimize
-  	if(last - first < detail::MIN_SORT_SIZE)
-  		std::sort(first, last, comp);
-  	else
-  		detail::reverse_string_sort(first, last, *first, unused);
-  }
-
-  //Top-level sorting call; wraps using default of unsigned char
-  template <class RandomAccessIter, class compare>
-  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp) 
-  {
-  	unsigned char unused = '\0';
-  	reverse_string_sort(first, last, comp, unused);
-  }
-
-  template <class RandomAccessIter, class get_char, class get_length>
-  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length) 
-  {
-  	//Don't sort if it's too small to optimize
-  	if(last - first < detail::MIN_SORT_SIZE)
-  		std::sort(first, last);
-  	else {
-  		//skipping past empties at the beginning, which allows us to get the character type 
-  		//.empty() is not used so as not to require a user declaration of it
-  		while(!length(*first)) {
-  			if(++first == last)
-  				return;
-  		}
-  		detail::string_sort(first, last, getchar, length, *first, getchar((*first), 0));
-  	}
-  }
-
-  template <class RandomAccessIter, class get_char, class get_length, class compare>
-  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 
-  {
-  	//Don't sort if it's too small to optimize
-  	if(last - first < detail::MIN_SORT_SIZE)
-  		std::sort(first, last, comp);
-  	else {
-  		//skipping past empties at the beginning, which allows us to get the character type 
-  		//.empty() is not used so as not to require a user declaration of it
-  		while(!length(*first)) {
-  			if(++first == last)
-  				return;
-  		}
-  		detail::string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
-  	}
-  }
-
-  template <class RandomAccessIter, class get_char, class get_length, class compare>
-  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 
-  {
-  	//Don't sort if it's too small to optimize
-  	if(last - first < detail::MIN_SORT_SIZE)
-  		std::sort(first, last, comp);
-  	else {
-  		//skipping past empties at the beginning, which allows us to get the character type 
-  		//.empty() is not used so as not to require a user declaration of it
-  		while(!length(*(--last))) {
-  			//Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order
-  			if(first == last)
-  				return;
-  		}
-  		//making last just after the end of the non-empty part of the array
-  		++last;
-  		detail::reverse_string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
-  	}
-  }
-}
-
-#endif
+//Templated spread_sort library
+
+//          Copyright Steven J. Ross 2001 - 2009.
+// Distributed under the Boost Software License, Version 1.0.
+//    (See accompanying file LICENSE_1_0.txt or copy at
+//          http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org/ for updates, documentation, and revision history.
+		  
+/*
+Some improvements suggested by:
+Phil Endecott and Frank Gennari
+Cygwin fix provided by:
+Scott McMurray
+*/
+
+#ifndef BOOST_SPREAD_SORT_H
+#define BOOST_SPREAD_SORT_H
+#include <algorithm>
+#include <cstring>
+#include <vector>
+#include "webrtc/system_wrappers/source/spreadsortlib/constants.hpp"
+
+#include <features.h>
+#if defined(__UCLIBC__)
+#undef getchar
+#endif
+
+
+namespace boost {
+  namespace detail {
+  	//This only works on unsigned data types
+  	template <typename T>
+  	inline unsigned 
+  	rough_log_2_size(const T& input) 
+  	{
+  		unsigned result = 0;
+  		//The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance
+  		while((input >> result) && (result < (8*sizeof(T)))) ++result;
+  		return result;
+  	}
+
+  	//Gets the maximum size which we'll call spread_sort on to control worst-case performance
+  	//Maintains both a minimum size to recurse and a check of distribution size versus count
+  	//This is called for a set of bins, instead of bin-by-bin, to avoid performance overhead
+  	inline size_t
+  	get_max_count(unsigned log_range, size_t count)
+  	{
+  		unsigned divisor = rough_log_2_size(count);
+  		//Making sure the divisor is positive
+  		if(divisor > LOG_MEAN_BIN_SIZE)
+  			divisor -= LOG_MEAN_BIN_SIZE;
+  		else
+  			divisor = 1;
+  		unsigned relative_width = (LOG_CONST * log_range)/((divisor > MAX_SPLITS) ? MAX_SPLITS : divisor);
+  		//Don't try to bitshift more than the size of an element
+  		if((8*sizeof(size_t)) <= relative_width)
+  			relative_width = (8*sizeof(size_t)) - 1;
+  		return (size_t)1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ? 
+  			(LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) :  relative_width);
+  	}
+
+  	//Find the minimum and maximum using <
+  	template <class RandomAccessIter>
+  	inline void 
+  	find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min)
+  	{
+  		min = max = current;
+  		//Start from the second item, as max and min are initialized to the first
+  		while(++current < last) {
+  			if(*max < *current)
+  				max = current;
+  			else if(*current < *min)
+  				min = current;
+  		}
+  	}
+
+  	//Uses a user-defined comparison operator to find minimum and maximum
+  	template <class RandomAccessIter, class compare>
+  	inline void 
+  	find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min, compare comp)
+  	{
+  		min = max = current;
+  		while(++current < last) {
+  			if(comp(*max, *current))
+  				max = current;
+  			else if(comp(*current, *min))
+  				min = current;
+  		}
+  	}
+
+  	//Gets a non-negative right bit shift to operate as a logarithmic divisor
+  	inline int
+  	get_log_divisor(size_t count, unsigned log_range)
+  	{
+  		int log_divisor;
+  		//If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so
+  		if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && log_range < MAX_SPLITS)
+  			log_divisor = 0;
+  		else {
+  			//otherwise divide the data into an optimized number of pieces
+  			log_divisor += LOG_MEAN_BIN_SIZE;
+  			if(log_divisor < 0)
+  				log_divisor = 0;
+  			//Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically
+  			if((log_range - log_divisor) > MAX_SPLITS)
+  				log_divisor = log_range - MAX_SPLITS;
+  		}
+  		return log_divisor;
+  	}
+
+  	template <class RandomAccessIter>
+  	inline RandomAccessIter * 
+  	size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
+  	{
+  		//Assure space for the size of each bin, followed by initializing sizes
+  		if(bin_count > bin_sizes.size())
+  			bin_sizes.resize(bin_count);
+  		for(size_t u = 0; u < bin_count; u++)
+  			bin_sizes[u] = 0;
+  		//Make sure there is space for the bins
+  		cache_end = cache_offset + bin_count;
+  		if(cache_end > bin_cache.size())
+  			bin_cache.resize(cache_end);
+  		return &(bin_cache[cache_offset]);
+  	}
+
+  	//Implementation for recursive integer sorting
+  	template <class RandomAccessIter, class div_type, class data_type>
+  	inline void 
+  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+  				  , std::vector<size_t> &bin_sizes)
+  	{
+  		//This step is roughly 10% of runtime, but it helps avoid worst-case behavior and improve behavior with real data
+  		//If you know the maximum and minimum ahead of time, you can pass those values in and skip this step for the first iteration
+  		RandomAccessIter max, min;
+  		find_extremes(first, last, max, min);
+  		//max and min will be the same (the first item) iff all values are equivalent
+  		if(max == min)
+  			return;
+  		RandomAccessIter * target_bin;
+  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(*max >> 0) - (*min >> 0)));
+  		div_type div_min = *min >> log_divisor;
+  		div_type div_max = *max >> log_divisor;
+  		unsigned bin_count = div_max - div_min + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+  	
+  		//Calculating the size of each bin; this takes roughly 10% of runtime
+  		for (RandomAccessIter current = first; current != last;)
+  			bin_sizes[(*(current++) >> log_divisor) - div_min]++;
+  		//Assign the bin positions
+  		bins[0] = first;
+  		for(unsigned u = 0; u < bin_count - 1; u++)
+  			bins[u + 1] = bins[u] + bin_sizes[u];
+  
+  		//Swap into place
+  		//This dominates runtime, mostly in the swap and bin lookups
+  		RandomAccessIter nextbinstart = first;
+  		for(unsigned u = 0; u < bin_count - 1; ++u) {
+  			RandomAccessIter * local_bin = bins + u;
+  			nextbinstart += bin_sizes[u];
+  			//Iterating over each element in this bin
+  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  				//Swapping elements in current into place until the correct element has been swapped in
+  				for(target_bin = (bins + ((*current >> log_divisor) - div_min));  target_bin != local_bin; 
+  					target_bin = bins + ((*current >> log_divisor) - div_min)) {
+  					//3-way swap; this is about 1% faster than a 2-way swap with integers
+  					//The main advantage is less copies are involved per item put in the correct place
+  					data_type tmp;
+  					RandomAccessIter b = (*target_bin)++;
+  					RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min);
+  					if (b_bin != local_bin) {
+  						RandomAccessIter c = (*b_bin)++;
+  						tmp = *c;
+  						*c = *b;
+  					} 
+  					else
+  						tmp = *b;
+  					*b = *current;
+  					*current = tmp;
+  				}
+  			}
+  			*local_bin = nextbinstart;
+  		}
+  		bins[bin_count - 1] = last;
+  
+  		//If we've bucketsorted, the array is sorted and we should skip recursion
+  		if(!log_divisor)
+  			return;
+  
+  		//Recursing; log_divisor is the remaining range
+  		size_t max_count = get_max_count(log_divisor, last - first);
+  		RandomAccessIter lastPos = first;
+  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			//don't sort unless there are at least two items to compare
+  			if(count < 2)
+  				continue;
+  			//using std::sort if its worst-case is better
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[u]);
+  			else
+  				spread_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
+  		}
+  	}
+
+  	//Generic bitshift-based 3-way swapping code
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+  	inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
+  		, const unsigned log_divisor, const div_type div_min) 
+  	{
+  		RandomAccessIter * local_bin = bins + ii;
+  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  			for(RandomAccessIter * target_bin = (bins + (shift(*current, log_divisor) - div_min));  target_bin != local_bin; 
+  				target_bin = bins + (shift(*current, log_divisor) - div_min)) {
+  				data_type tmp;
+  				RandomAccessIter b = (*target_bin)++;
+  				RandomAccessIter * b_bin = bins + (shift(*b, log_divisor) - div_min);
+  				//Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
+  				if (b_bin != local_bin) {
+  					RandomAccessIter c = (*b_bin)++;
+  					tmp = *c;
+  					*c = *b;
+  				} 
+  				//Note: we could increment current once the swap is done in this case, but that seems to impair performance
+  				else
+  					tmp = *b;
+  				*b = *current;
+  				*current = tmp;
+  			}
+  		}
+  		*local_bin = nextbinstart;
+  	}
+
+  	//Standard swapping wrapper for ascending values
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+  	inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
+  		, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 
+  	{
+  		nextbinstart += bin_sizes[ii];
+  		inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, log_divisor, div_min);
+  	}
+
+  	//Functor implementation for recursive sorting
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+  	inline void 
+  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
+  	{
+  		RandomAccessIter max, min;
+  		find_extremes(first, last, max, min, comp);
+  		if(max == min)
+  			return;
+  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
+  		div_type div_min = shift(*min, log_divisor);
+  		div_type div_max = shift(*max, log_divisor);
+  		unsigned bin_count = div_max - div_min + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+  			
+  		//Calculating the size of each bin
+  		for (RandomAccessIter current = first; current != last;)
+  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+  		bins[0] = first;
+  		for(unsigned u = 0; u < bin_count - 1; u++)
+  			bins[u + 1] = bins[u] + bin_sizes[u];
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		for(unsigned u = 0; u < bin_count - 1; ++u)
+  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min);
+  		bins[bin_count - 1] = last;
+  		
+  		//If we've bucketsorted, the array is sorted and we should skip recursion
+  		if(!log_divisor)
+  			return;
+  		
+  		//Recursing
+  		size_t max_count = get_max_count(log_divisor, last - first);
+  		RandomAccessIter lastPos = first;
+  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[u], comp);
+  			else
+  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
+  		}
+  	}
+
+  	//Functor implementation for recursive sorting with only Shift overridden
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+  	inline void 
+  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+  					, std::vector<size_t> &bin_sizes, right_shift shift)
+  	{
+  		RandomAccessIter max, min;
+  		find_extremes(first, last, max, min);
+  		if(max == min)
+  			return;
+  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
+  		div_type div_min = shift(*min, log_divisor);
+  		div_type div_max = shift(*max, log_divisor);
+  		unsigned bin_count = div_max - div_min + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+  			
+  		//Calculating the size of each bin
+  		for (RandomAccessIter current = first; current != last;)
+  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+  		bins[0] = first;
+  		for(unsigned u = 0; u < bin_count - 1; u++)
+  			bins[u + 1] = bins[u] + bin_sizes[u];
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		for(unsigned ii = 0; ii < bin_count - 1; ++ii)
+  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
+  		bins[bin_count - 1] = last;
+  		
+  		//If we've bucketsorted, the array is sorted and we should skip recursion
+  		if(!log_divisor)
+  			return;
+  		
+  		//Recursing
+  		size_t max_count = get_max_count(log_divisor, last - first);
+  		RandomAccessIter lastPos = first;
+  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[u]);
+  			else
+  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
+  		}
+  	}
+
+  	//Holds the bin vector and makes the initial recursive call
+  	template <class RandomAccessIter, class div_type, class data_type>
+  	inline void 
+  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type)
+  	{
+  		std::vector<size_t> bin_sizes;
+  		std::vector<RandomAccessIter> bin_cache;
+  		spread_sort_rec<RandomAccessIter, div_type, data_type>(first, last, bin_cache, 0, bin_sizes);
+  	}
+
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+  	inline void 
+  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
+  	{
+  		std::vector<size_t> bin_sizes;
+  		std::vector<RandomAccessIter> bin_cache;
+  		spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp);
+  	}
+
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+  	inline void 
+  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
+  	{
+  		std::vector<size_t> bin_sizes;
+  		std::vector<RandomAccessIter> bin_cache;
+  		spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
+  	}
+  }
+
+  //Top-level sorting call for integers
+  template <class RandomAccessIter>
+  inline void integer_sort(RandomAccessIter first, RandomAccessIter last) 
+  {
+  	//Don't sort if it's too small to optimize
+  	if(last - first < detail::MIN_SORT_SIZE)
+  		std::sort(first, last);
+  	else
+  		detail::spread_sort(first, last, *first >> 0, *first);
+  }
+
+  //integer_sort with functors
+  template <class RandomAccessIter, class right_shift, class compare>
+  inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
+  						right_shift shift, compare comp) {
+  	if(last - first < detail::MIN_SORT_SIZE)
+  		std::sort(first, last, comp);
+  	else
+  		detail::spread_sort(first, last, shift(*first, 0), *first, shift, comp);
+  }
+
+  //integer_sort with right_shift functor
+  template <class RandomAccessIter, class right_shift>
+  inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
+  						right_shift shift) {
+  	if(last - first < detail::MIN_SORT_SIZE)
+  		std::sort(first, last);
+  	else
+  		detail::spread_sort(first, last, shift(*first, 0), *first, shift);
+  }
+
+  //------------------------------------------------------ float_sort source --------------------------------------
+  //Casts a RandomAccessIter to the specified data type
+  template<class cast_type, class RandomAccessIter>
+  inline cast_type
+  cast_float_iter(const RandomAccessIter & floatiter)
+  {
+  	cast_type result;
+  	std::memcpy(&result, &(*floatiter), sizeof(cast_type));
+  	return result;
+  }
+
+  //Casts a data element to the specified datinner_float_a type
+  template<class data_type, class cast_type>
+  inline cast_type
+  mem_cast(const data_type & data)
+  {
+  	cast_type result;
+  	std::memcpy(&result, &data, sizeof(cast_type));
+  	return result;
+  }
+
+  namespace detail {
+  	template <class RandomAccessIter, class div_type, class right_shift>
+  	inline void 
+  	find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift)
+  	{
+  		min = max = shift(*current, 0);
+  		while(++current < last) {
+  			div_type value = shift(*current, 0);
+  			if(max < value)
+  				max = value;
+  			else if(value < min)
+  				min = value;
+  		}
+  	}
+
+  	//Specialized swap loops for floating-point casting
+  	template <class RandomAccessIter, class div_type, class data_type>
+  	inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii
+  		, const unsigned log_divisor, const div_type div_min) 
+  	{
+  		RandomAccessIter * local_bin = bins + ii;
+  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  			for(RandomAccessIter * target_bin = (bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min));  target_bin != local_bin; 
+  				target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) {
+  				data_type tmp;
+  				RandomAccessIter b = (*target_bin)++;
+  				RandomAccessIter * b_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(b) >> log_divisor) - div_min);
+  				//Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
+  				if (b_bin != local_bin) {
+  					RandomAccessIter c = (*b_bin)++;
+  					tmp = *c;
+  					*c = *b;
+  				} 
+  				else
+  					tmp = *b;
+  				*b = *current;
+  				*current = tmp;
+  			}
+  		}
+  		*local_bin = nextbinstart;
+  	}
+
+  	template <class RandomAccessIter, class div_type, class data_type>
+  	inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii
+  		, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 
+  	{
+  		nextbinstart += bin_sizes[ii];
+  		inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, log_divisor, div_min);
+  	}
+
+  	template <class RandomAccessIter, class cast_type>
+  	inline void 
+  	find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min)
+  	{
+  		min = max = cast_float_iter<cast_type, RandomAccessIter>(current);
+  		while(++current < last) {
+  			cast_type value = cast_float_iter<cast_type, RandomAccessIter>(current);
+  			if(max < value)
+  				max = value;
+  			else if(value < min)
+  				min = value;
+  		}
+  	}
+
+  	//Special-case sorting of positive floats with casting instead of a right_shift
+  	template <class RandomAccessIter, class div_type, class data_type>
+  	inline void 
+  	positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+  					, std::vector<size_t> &bin_sizes)
+  	{
+  		div_type max, min;
+  		find_extremes(first, last, max, min);
+  		if(max == min)
+  			return;
+  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+  		div_type div_min = min >> log_divisor;
+  		div_type div_max = max >> log_divisor;
+  		unsigned bin_count = div_max - div_min + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+  			
+  		//Calculating the size of each bin
+  		for (RandomAccessIter current = first; current != last;)
+  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
+  		bins[0] = first;
+  		for(unsigned u = 0; u < bin_count - 1; u++)
+  			bins[u + 1] = bins[u] + bin_sizes[u];
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		for(unsigned u = 0; u < bin_count - 1; ++u)
+  			float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, bin_sizes, log_divisor, div_min);
+  		bins[bin_count - 1] = last;
+  		
+  		//Return if we've completed bucketsorting
+  		if(!log_divisor)
+  			return;
+  		
+  		//Recursing
+  		size_t max_count = get_max_count(log_divisor, last - first);
+  		RandomAccessIter lastPos = first;
+  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[u]);
+  			else
+  				positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
+  		}
+  	}
+
+  	//Sorting negative_ float_s
+  	//Note that bins are iterated in reverse order because max_neg_float = min_neg_int
+  	template <class RandomAccessIter, class div_type, class data_type>
+  	inline void 
+  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+  					, std::vector<size_t> &bin_sizes)
+  	{
+  		div_type max, min;
+  		find_extremes(first, last, max, min);
+  		if(max == min)
+  			return;
+  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+  		div_type div_min = min >> log_divisor;
+  		div_type div_max = max >> log_divisor;
+  		unsigned bin_count = div_max - div_min + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+  			
+  		//Calculating the size of each bin
+  		for (RandomAccessIter current = first; current != last;)
+  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
+  		bins[bin_count - 1] = first;
+  		for(int ii = bin_count - 2; ii >= 0; --ii)
+  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		//The last bin will always have the correct elements in it
+  		for(int ii = bin_count - 1; ii > 0; --ii)
+  			float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);
+  		//Since we don't process the last bin, we need to update its end position
+  		bin_cache[cache_offset] = last;
+  		
+  		//Return if we've completed bucketsorting
+  		if(!log_divisor)
+  			return;
+  		
+  		//Recursing
+  		size_t max_count = get_max_count(log_divisor, last - first);
+  		RandomAccessIter lastPos = first;
+  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
+  			size_t count = bin_cache[ii] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[ii]);
+  			else
+  				negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
+  		}
+  	}
+
+  	//Sorting negative_ float_s
+  	//Note that bins are iterated in reverse order because max_neg_float = min_neg_int
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+  	inline void 
+  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+  					, std::vector<size_t> &bin_sizes, right_shift shift)
+  	{
+  		div_type max, min;
+  		find_extremes(first, last, max, min, shift);
+  		if(max == min)
+  			return;
+  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+  		div_type div_min = min >> log_divisor;
+  		div_type div_max = max >> log_divisor;
+  		unsigned bin_count = div_max - div_min + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+  			
+  		//Calculating the size of each bin
+  		for (RandomAccessIter current = first; current != last;)
+  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+  		bins[bin_count - 1] = first;
+  		for(int ii = bin_count - 2; ii >= 0; --ii)
+  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		//The last bin will always have the correct elements in it
+  		for(int ii = bin_count - 1; ii > 0; --ii)
+  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
+  		//Since we don't process the last bin, we need to update its end position
+  		bin_cache[cache_offset] = last;
+  		
+  		//Return if we've completed bucketsorting
+  		if(!log_divisor)
+  			return;
+  		
+  		//Recursing
+  		size_t max_count = get_max_count(log_divisor, last - first);
+  		RandomAccessIter lastPos = first;
+  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
+  			size_t count = bin_cache[ii] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[ii]);
+  			else
+  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
+  		}
+  	}
+
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+  	inline void 
+  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
+  	{
+  		div_type max, min;
+  		find_extremes(first, last, max, min, shift);
+  		if(max == min)
+  			return;
+  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+  		div_type div_min = min >> log_divisor;
+  		div_type div_max = max >> log_divisor;
+  		unsigned bin_count = div_max - div_min + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+  			
+  		//Calculating the size of each bin
+  		for (RandomAccessIter current = first; current != last;)
+  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+  		bins[bin_count - 1] = first;
+  		for(int ii = bin_count - 2; ii >= 0; --ii)
+  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		//The last bin will always have the correct elements in it
+  		for(int ii = bin_count - 1; ii > 0; --ii)
+  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
+  		//Since we don't process the last bin, we need to update its end position
+  		bin_cache[cache_offset] = last;
+  		
+  		//Return if we've completed bucketsorting
+  		if(!log_divisor)
+  			return;
+  		
+  		//Recursing
+  		size_t max_count = get_max_count(log_divisor, last - first);
+  		RandomAccessIter lastPos = first;
+  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
+  			size_t count = bin_cache[ii] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[ii], comp);
+  			else
+  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
+  		}
+  	}
+
+  	//Casting special-case for floating-point sorting
+  	template <class RandomAccessIter, class div_type, class data_type>
+  	inline void 
+  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+  					, std::vector<size_t> &bin_sizes)
+  	{
+  		div_type max, min;
+  		find_extremes(first, last, max, min);
+  		if(max == min)
+  			return;
+  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+  		div_type div_min = min >> log_divisor;
+  		div_type div_max = max >> log_divisor;
+  		unsigned bin_count = div_max - div_min + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+  			
+  		//Calculating the size of each bin
+  		for (RandomAccessIter current = first; current != last;)
+  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
+  		//The index of the first positive bin
+  		div_type first_positive = (div_min < 0) ? -div_min : 0;
+  		//Resetting if all bins are negative
+  		if(cache_offset + first_positive > cache_end)
+  			first_positive = cache_end - cache_offset;
+  		//Reversing the order of the negative bins
+  		//Note that because of the negative/positive ordering direction flip
+  		//We can not depend upon bin order and positions matching up
+  		//so bin_sizes must be reused to contain the end of the bin
+  		if(first_positive > 0) {
+  			bins[first_positive - 1] = first;
+  			for(int ii = first_positive - 2; ii >= 0; --ii) {
+  				bins[ii] = first + bin_sizes[ii + 1];
+  				bin_sizes[ii] += bin_sizes[ii + 1];
+  			}
+  			//Handling positives following negatives
+  			if((unsigned)first_positive < bin_count) {
+  				bins[first_positive] = first + bin_sizes[0];
+  				bin_sizes[first_positive] += bin_sizes[0];
+  			}
+  		}
+  		else
+  			bins[0] = first;
+  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
+  			bins[u + 1] = first + bin_sizes[u];
+  			bin_sizes[u + 1] += bin_sizes[u];
+  		}
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		for(unsigned u = 0; u < bin_count; ++u) {
+  			nextbinstart = first + bin_sizes[u];
+  			inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, log_divisor, div_min);
+  		}
+  		
+  		if(!log_divisor)
+  			return;
+  		
+  		//Handling negative values first
+  		size_t max_count = get_max_count(log_divisor, last - first);
+  		RandomAccessIter lastPos = first;
+  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
+  			size_t count = bin_cache[ii] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[ii]);
+  			//sort negative values using reversed-bin spread_sort
+  			else
+  				negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
+  		}
+  		
+  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[u]);
+  			//sort positive values using normal spread_sort
+  			else
+  				positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
+  		}
+  	}
+
+  	//Functor implementation for recursive sorting
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+  	inline void 
+  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+  					, std::vector<size_t> &bin_sizes, right_shift shift)
+  	{
+  		div_type max, min;
+  		find_extremes(first, last, max, min, shift);
+  		if(max == min)
+  			return;
+  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+  		div_type div_min = min >> log_divisor;
+  		div_type div_max = max >> log_divisor;
+  		unsigned bin_count = div_max - div_min + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+  			
+  		//Calculating the size of each bin
+  		for (RandomAccessIter current = first; current != last;)
+  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+  		//The index of the first positive bin
+  		div_type first_positive = (div_min < 0) ? -div_min : 0;
+  		//Resetting if all bins are negative
+  		if(cache_offset + first_positive > cache_end)
+  			first_positive = cache_end - cache_offset;
+  		//Reversing the order of the negative bins
+  		//Note that because of the negative/positive ordering direction flip
+  		//We can not depend upon bin order and positions matching up
+  		//so bin_sizes must be reused to contain the end of the bin
+  		if(first_positive > 0) {
+  			bins[first_positive - 1] = first;
+  			for(int ii = first_positive - 2; ii >= 0; --ii) {
+  				bins[ii] = first + bin_sizes[ii + 1];
+  				bin_sizes[ii] += bin_sizes[ii + 1];
+  			}
+  			//Handling positives following negatives
+  			if((unsigned)first_positive < bin_count) {
+  				bins[first_positive] = first + bin_sizes[0];
+  				bin_sizes[first_positive] += bin_sizes[0];
+  			}
+  		}
+  		else
+  			bins[0] = first;
+  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
+  			bins[u + 1] = first + bin_sizes[u];
+  			bin_sizes[u + 1] += bin_sizes[u];
+  		}
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		for(unsigned u = 0; u < bin_count; ++u) {
+  			nextbinstart = first + bin_sizes[u];
+  			inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
+  		}
+  		
+  		//Return if we've completed bucketsorting
+  		if(!log_divisor)
+  			return;
+  		
+  		//Handling negative values first
+  		size_t max_count = get_max_count(log_divisor, last - first);
+  		RandomAccessIter lastPos = first;
+  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
+  			size_t count = bin_cache[ii] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[ii]);
+  			//sort negative values using reversed-bin spread_sort
+  			else
+  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
+  		}
+  		
+  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[u]);
+  			//sort positive values using normal spread_sort
+  			else
+  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
+  		}
+  	}
+
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+  	inline void 
+  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
+  	{
+  		div_type max, min;
+  		find_extremes(first, last, max, min, shift);
+  		if(max == min)
+  			return;
+  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+  		div_type div_min = min >> log_divisor;
+  		div_type div_max = max >> log_divisor;
+  		unsigned bin_count = div_max - div_min + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+  			
+  		//Calculating the size of each bin
+  		for (RandomAccessIter current = first; current != last;)
+  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+  		//The index of the first positive bin
+  		div_type first_positive = (div_min < 0) ? -div_min : 0;
+  		//Resetting if all bins are negative
+  		if(cache_offset + first_positive > cache_end)
+  			first_positive = cache_end - cache_offset;
+  		//Reversing the order of the negative bins
+  		//Note that because of the negative/positive ordering direction flip
+  		//We can not depend upon bin order and positions matching up
+  		//so bin_sizes must be reused to contain the end of the bin
+  		if(first_positive > 0) {
+  			bins[first_positive - 1] = first;
+  			for(int ii = first_positive - 2; ii >= 0; --ii) {
+  				bins[ii] = first + bin_sizes[ii + 1];
+  				bin_sizes[ii] += bin_sizes[ii + 1];
+  			}
+  			//Handling positives following negatives
+  			if((unsigned)first_positive < bin_count) {
+  				bins[first_positive] = first + bin_sizes[0];
+  				bin_sizes[first_positive] += bin_sizes[0];
+  			}
+  		}
+  		else
+  			bins[0] = first;
+  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
+  			bins[u + 1] = first + bin_sizes[u];
+  			bin_sizes[u + 1] += bin_sizes[u];
+  		}
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		for(unsigned u = 0; u < bin_count; ++u) {
+  			nextbinstart = first + bin_sizes[u];
+  			inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
+  		}
+  		
+  		//Return if we've completed bucketsorting
+  		if(!log_divisor)
+  			return;
+  		
+  		//Handling negative values first
+  		size_t max_count = get_max_count(log_divisor, last - first);
+  		RandomAccessIter lastPos = first;
+  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
+  			size_t count = bin_cache[ii] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[ii]);
+  			//sort negative values using reversed-bin spread_sort
+  			else
+  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
+  		}
+  		
+  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			if(count < 2)
+  				continue;
+  			if(count < max_count)
+  				std::sort(lastPos, bin_cache[u]);
+  			//sort positive values using normal spread_sort
+  			else
+  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
+  		}
+  	}
+
+  	template <class RandomAccessIter, class cast_type, class data_type>
+  	inline void 
+  	float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, data_type)
+  	{
+  		std::vector<size_t> bin_sizes;
+  		std::vector<RandomAccessIter> bin_cache;
+  		float_sort_rec<RandomAccessIter, cast_type, data_type>(first, last, bin_cache, 0, bin_sizes);
+  	}
+
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+  	inline void 
+  	float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
+  	{
+  		std::vector<size_t> bin_sizes;
+  		std::vector<RandomAccessIter> bin_cache;
+  		float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
+  	}
+
+  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+  	inline void 
+  	float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
+  	{
+  		std::vector<size_t> bin_sizes;
+  		std::vector<RandomAccessIter> bin_cache;
+  		float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift, comp);
+  	}
+  }
+
+  //float_sort with casting
+  //The cast_type must be equal in size to the data type, and must be a signed integer
+  template <class RandomAccessIter, class cast_type>
+  inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cast_type cVal) 
+  {
+  	if(last - first < detail::MIN_SORT_SIZE)
+  		std::sort(first, last);
+  	else
+  		detail::float_Sort(first, last, cVal, *first);
+  }
+
+  //float_sort with casting to an int
+  //Only use this with IEEE floating-point numbers
+  template <class RandomAccessIter>
+  inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter last) 
+  {
+  	int cVal = 0;
+  	float_sort_cast(first, last, cVal);
+  }
+
+  //float_sort with functors
+  template <class RandomAccessIter, class right_shift>
+  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift) 
+  {
+  	if(last - first < detail::MIN_SORT_SIZE)
+  		std::sort(first, last);
+  	else
+  		detail::float_Sort(first, last, shift(*first, 0), *first, shift);
+  }
+
+  template <class RandomAccessIter, class right_shift, class compare>
+  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift, compare comp) 
+  {
+  	if(last - first < detail::MIN_SORT_SIZE)
+  		std::sort(first, last, comp);
+  	else
+  		detail::float_Sort(first, last, shift(*first, 0), *first, shift, comp);
+  }
+
+  //------------------------------------------------- string_sort source ---------------------------------------------
+  namespace detail {
+  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.
+  	template<class RandomAccessIter>
+  	inline void
+  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset)
+  	{
+  		unsigned nextOffset = char_offset;
+  		bool done = false;
+  		while(!done) {
+  			RandomAccessIter curr = first;
+  			do {
+  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
+  				if((*curr).size() > char_offset && ((*curr).size() <= (nextOffset + 1) || (*curr)[nextOffset] != (*first)[nextOffset])) {
+  					done = true;
+  					break;
+  				}
+  			} while(++curr != finish);
+  			if(!done)
+  				++nextOffset;
+  		} 
+  		char_offset = nextOffset;
+  	}
+
+  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.
+  	template<class RandomAccessIter, class get_char, class get_length>
+  	inline void
+  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length)
+  	{
+  		unsigned nextOffset = char_offset;
+  		bool done = false;
+  		while(!done) {
+  			RandomAccessIter curr = first;
+  			do {
+  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
+  				if(length(*curr) > char_offset && (length(*curr) <= (nextOffset + 1) || getchar((*curr), nextOffset) != getchar((*first), nextOffset))) {
+  					done = true;
+  					break;
+  				}
+  			} while(++curr != finish);
+  			if(!done)
+  				++nextOffset;
+  		} 
+  		char_offset = nextOffset;
+  	}
+
+  	//A comparison functor for strings that assumes they are identical up to char_offset
+  	template<class data_type, class unsignedchar_type>
+  	struct offset_lessthan {
+  		offset_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
+  		inline bool operator()(const data_type &x, const data_type &y) const 
+  		{
+  			unsigned minSize = std::min(x.size(), y.size());
+  			for(unsigned u = fchar_offset; u < minSize; ++u) {
+  				if(static_cast<unsignedchar_type>(x[u]) < static_cast<unsignedchar_type>(y[u]))
+  					return true;
+  				else if(static_cast<unsignedchar_type>(y[u]) < static_cast<unsignedchar_type>(x[u]))
+  					return false;
+  			}
+  			return x.size() < y.size();
+  		}
+  		unsigned fchar_offset;
+  	};
+
+  	//A comparison functor for strings that assumes they are identical up to char_offset
+  	template<class data_type, class unsignedchar_type>
+  	struct offset_greaterthan {
+  		offset_greaterthan(unsigned char_offset) : fchar_offset(char_offset){}
+  		inline bool operator()(const data_type &x, const data_type &y) const 
+  		{
+  			unsigned minSize = std::min(x.size(), y.size());
+  			for(unsigned u = fchar_offset; u < minSize; ++u) {
+  				if(static_cast<unsignedchar_type>(x[u]) > static_cast<unsignedchar_type>(y[u]))
+  					return true;
+  				else if(static_cast<unsignedchar_type>(y[u]) > static_cast<unsignedchar_type>(x[u]))
+  					return false;
+  			}
+  			return x.size() > y.size();
+  		}
+  		unsigned fchar_offset;
+  	};
+
+  	//A comparison functor for strings that assumes they are identical up to char_offset
+  	template<class data_type, class get_char, class get_length>
+  	struct offset_char_lessthan {
+  		offset_char_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
+  		inline bool operator()(const data_type &x, const data_type &y) const 
+  		{
+  			unsigned minSize = std::min(length(x), length(y));
+  			for(unsigned u = fchar_offset; u < minSize; ++u) {
+  				if(getchar(x, u) < getchar(y, u))
+  					return true;
+  				else if(getchar(y, u) < getchar(x, u))
+  					return false;
+  			}
+  			return length(x) < length(y);
+  		}
+  		unsigned fchar_offset;
+  		get_char getchar;
+  		get_length length;
+  	};
+
+  	//String sorting recursive implementation
+  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
+  	inline void 
+  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)
+  	{
+  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+  		//Iterate to the end of the empties.  If all empty, return
+  		while((*first).size() <= char_offset) {
+  			if(++first == last)
+  				return;
+  		}
+  		RandomAccessIter finish = last - 1;
+  		//Getting the last non-empty
+  		for(;(*finish).size() <= char_offset; --finish) { }
+  		++finish;
+  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
+  		update_offset(first, finish, char_offset);
+  		
+  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+  		const unsigned max_size = bin_count;
+  		const unsigned membin_count = bin_count + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
+  			
+  		//Calculating the size of each bin; this takes roughly 10% of runtime
+  		for (RandomAccessIter current = first; current != last; ++current) {
+  			if((*current).size() <= char_offset) {
+  				bin_sizes[0]++;
+  			}
+  			else
+  				bin_sizes[static_cast<unsignedchar_type>((*current)[char_offset]) + 1]++;
+  		}
+  		//Assign the bin positions
+  		bin_cache[cache_offset] = first;
+  		for(unsigned u = 0; u < membin_count - 1; u++)
+  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		//handling empty bins
+  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
+  		nextbinstart +=	bin_sizes[0];
+  		RandomAccessIter * target_bin;
+  		//Iterating over each element in the bin of empties
+  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  			//empties belong in this bin
+  			while((*current).size() > char_offset) {
+  				target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);
+  				iter_swap(current, (*target_bin)++);
+  			}
+  		}
+  		*local_bin = nextbinstart;
+  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+  		unsigned last_bin = bin_count - 1;
+  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
+  		//This dominates runtime, mostly in the swap and bin lookups
+  		for(unsigned u = 0; u < last_bin; ++u) {
+  			local_bin = bins + u;
+  			nextbinstart += bin_sizes[u + 1];
+  			//Iterating over each element in this bin
+  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  				//Swapping elements in current into place until the correct element has been swapped in
+  				for(target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 
+  					target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]))
+  					iter_swap(current, (*target_bin)++);
+  			}
+  			*local_bin = nextbinstart;
+  		}
+  		bins[last_bin] = last;
+  		//Recursing
+  		RandomAccessIter lastPos = bin_cache[cache_offset];
+  		//Skip this loop for empties
+  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			//don't sort unless there are at least two items to compare
+  			if(count < 2)
+  				continue;
+  			//using std::sort if its worst-case is better
+  			if(count < max_size)
+  				std::sort(lastPos, bin_cache[u], offset_lessthan<data_type, unsignedchar_type>(char_offset + 1));
+  			else
+  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
+  		}
+  	}
+
+  	//Sorts strings in reverse order, with empties at the end
+  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
+  	inline void 
+  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)
+  	{
+  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+  		RandomAccessIter curr = first;
+  		//Iterate to the end of the empties.  If all empty, return
+  		while((*curr).size() <= char_offset) {
+  			if(++curr == last)
+  				return;
+  		}
+  		//Getting the last non-empty
+  		while((*(--last)).size() <= char_offset) { }
+  		++last;
+  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
+  		update_offset(curr, last, char_offset);
+  		RandomAccessIter * target_bin;
+  		
+  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+  		const unsigned max_size = bin_count;
+  		const unsigned membin_count = bin_count + 1;
+  		const unsigned max_bin = bin_count - 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
+  		RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin]);
+  			
+  		//Calculating the size of each bin; this takes roughly 10% of runtime
+  		for (RandomAccessIter current = first; current != last; ++current) {
+  			if((*current).size() <= char_offset) {
+  				bin_sizes[bin_count]++;
+  			}
+  			else
+  				bin_sizes[max_bin - static_cast<unsignedchar_type>((*current)[char_offset])]++;
+  		}
+  		//Assign the bin positions
+  		bin_cache[cache_offset] = first;
+  		for(unsigned u = 0; u < membin_count - 1; u++)
+  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = last;
+  		//handling empty bins
+  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
+  		RandomAccessIter lastFull = *local_bin;
+  		//Iterating over each element in the bin of empties
+  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  			//empties belong in this bin
+  			while((*current).size() > char_offset) {
+  				target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);
+  				iter_swap(current, (*target_bin)++);
+  			}
+  		}
+  		*local_bin = nextbinstart;
+  		nextbinstart = first;
+  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+  		unsigned last_bin = max_bin;
+  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
+  		//This dominates runtime, mostly in the swap and bin lookups
+  		for(unsigned u = 0; u < last_bin; ++u) {
+  			local_bin = bins + u;
+  			nextbinstart += bin_sizes[u];
+  			//Iterating over each element in this bin
+  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  				//Swapping elements in current into place until the correct element has been swapped in
+  				for(target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 
+  					target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]))
+  					iter_swap(current, (*target_bin)++);
+  			}
+  			*local_bin = nextbinstart;
+  		}
+  		bins[last_bin] = lastFull;
+  		//Recursing
+  		RandomAccessIter lastPos = first;
+  		//Skip this loop for empties
+  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			//don't sort unless there are at least two items to compare
+  			if(count < 2)
+  				continue;
+  			//using std::sort if its worst-case is better
+  			if(count < max_size)
+  				std::sort(lastPos, bin_cache[u], offset_greaterthan<data_type, unsignedchar_type>(char_offset + 1));
+  			else
+  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
+  		}
+  	}
+
+  	//String sorting recursive implementation
+  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length>
+  	inline void 
+  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length)
+  	{
+  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+  		//Iterate to the end of the empties.  If all empty, return
+  		while(length(*first) <= char_offset) {
+  			if(++first == last)
+  				return;
+  		}
+  		RandomAccessIter finish = last - 1;
+  		//Getting the last non-empty
+  		for(;length(*finish) <= char_offset; --finish) { }
+  		++finish;
+  		update_offset(first, finish, char_offset, getchar, length);
+  		
+  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+  		const unsigned max_size = bin_count;
+  		const unsigned membin_count = bin_count + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
+  			
+  		//Calculating the size of each bin; this takes roughly 10% of runtime
+  		for (RandomAccessIter current = first; current != last; ++current) {
+  			if(length(*current) <= char_offset) {
+  				bin_sizes[0]++;
+  			}
+  			else
+  				bin_sizes[getchar((*current), char_offset) + 1]++;
+  		}
+  		//Assign the bin positions
+  		bin_cache[cache_offset] = first;
+  		for(unsigned u = 0; u < membin_count - 1; u++)
+  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		//handling empty bins
+  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
+  		nextbinstart +=	bin_sizes[0];
+  		RandomAccessIter * target_bin;
+  		//Iterating over each element in the bin of empties
+  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  			//empties belong in this bin
+  			while(length(*current) > char_offset) {
+  				target_bin = bins + getchar((*current), char_offset);
+  				iter_swap(current, (*target_bin)++);
+  			}
+  		}
+  		*local_bin = nextbinstart;
+  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+  		unsigned last_bin = bin_count - 1;
+  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
+  		//This dominates runtime, mostly in the swap and bin lookups
+  		for(unsigned ii = 0; ii < last_bin; ++ii) {
+  			local_bin = bins + ii;
+  			nextbinstart += bin_sizes[ii + 1];
+  			//Iterating over each element in this bin
+  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  				//Swapping elements in current into place until the correct element has been swapped in
+  				for(target_bin = bins + getchar((*current), char_offset);  target_bin != local_bin; 
+  					target_bin = bins + getchar((*current), char_offset))
+  					iter_swap(current, (*target_bin)++);
+  			}
+  			*local_bin = nextbinstart;
+  		}
+  		bins[last_bin] = last;
+  		
+  		//Recursing
+  		RandomAccessIter lastPos = bin_cache[cache_offset];
+  		//Skip this loop for empties
+  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			//don't sort unless there are at least two items to compare
+  			if(count < 2)
+  				continue;
+  			//using std::sort if its worst-case is better
+  			if(count < max_size)
+  				std::sort(lastPos, bin_cache[u], offset_char_lessthan<data_type, get_char, get_length>(char_offset + 1));
+  			else
+  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length);
+  		}
+  	}
+
+  	//String sorting recursive implementation
+  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
+  	inline void 
+  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
+  	{
+  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+  		//Iterate to the end of the empties.  If all empty, return
+  		while(length(*first) <= char_offset) {
+  			if(++first == last)
+  				return;
+  		}
+  		RandomAccessIter finish = last - 1;
+  		//Getting the last non-empty
+  		for(;length(*finish) <= char_offset; --finish) { }
+  		++finish;
+  		update_offset(first, finish, char_offset, getchar, length);
+  		
+  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+  		const unsigned max_size = bin_count;
+  		const unsigned membin_count = bin_count + 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
+  			
+  		//Calculating the size of each bin; this takes roughly 10% of runtime
+  		for (RandomAccessIter current = first; current != last; ++current) {
+  			if(length(*current) <= char_offset) {
+  				bin_sizes[0]++;
+  			}
+  			else
+  				bin_sizes[getchar((*current), char_offset) + 1]++;
+  		}
+  		//Assign the bin positions
+  		bin_cache[cache_offset] = first;
+  		for(unsigned u = 0; u < membin_count - 1; u++)
+  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = first;
+  		//handling empty bins
+  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
+  		nextbinstart +=	bin_sizes[0];
+  		RandomAccessIter * target_bin;
+  		//Iterating over each element in the bin of empties
+  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  			//empties belong in this bin
+  			while(length(*current) > char_offset) {
+  				target_bin = bins + getchar((*current), char_offset);
+  				iter_swap(current, (*target_bin)++);
+  			}
+  		}
+  		*local_bin = nextbinstart;
+  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+  		unsigned last_bin = bin_count - 1;
+  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
+  		//This dominates runtime, mostly in the swap and bin lookups
+  		for(unsigned u = 0; u < last_bin; ++u) {
+  			local_bin = bins + u;
+  			nextbinstart += bin_sizes[u + 1];
+  			//Iterating over each element in this bin
+  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  				//Swapping elements in current into place until the correct element has been swapped in
+  				for(target_bin = bins + getchar((*current), char_offset);  target_bin != local_bin; 
+  					target_bin = bins + getchar((*current), char_offset))
+  					iter_swap(current, (*target_bin)++);
+  			}
+  			*local_bin = nextbinstart;
+  		}
+  		bins[last_bin] = last;
+  		
+  		//Recursing
+  		RandomAccessIter lastPos = bin_cache[cache_offset];
+  		//Skip this loop for empties
+  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			//don't sort unless there are at least two items to compare
+  			if(count < 2)
+  				continue;
+  			//using std::sort if its worst-case is better
+  			if(count < max_size)
+  				std::sort(lastPos, bin_cache[u], comp);
+  			else
+  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
+  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
+  		}
+  	}
+
+  	//Sorts strings in reverse order, with empties at the end
+  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
+  	inline void 
+  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
+  	{
+  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+  		RandomAccessIter curr = first;
+  		//Iterate to the end of the empties.  If all empty, return
+  		while(length(*curr) <= char_offset) {
+  			if(++curr == last)
+  				return;
+  		}
+  		//Getting the last non-empty
+  		while(length(*(--last)) <= char_offset) { }
+  		++last;
+  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
+  		update_offset(first, last, char_offset, getchar, length);
+  		
+  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+  		const unsigned max_size = bin_count;
+  		const unsigned membin_count = bin_count + 1;
+  		const unsigned max_bin = bin_count - 1;
+  		unsigned cache_end;
+  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
+  		RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]);
+  			
+  		//Calculating the size of each bin; this takes roughly 10% of runtime
+  		for (RandomAccessIter current = first; current != last; ++current) {
+  			if(length(*current) <= char_offset) {
+  				bin_sizes[bin_count]++;
+  			}
+  			else
+  				bin_sizes[max_bin - getchar((*current), char_offset)]++;
+  		}
+  		//Assign the bin positions
+  		bin_cache[cache_offset] = first;
+  		for(unsigned u = 0; u < membin_count - 1; u++)
+  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+  		
+  		//Swap into place
+  		RandomAccessIter nextbinstart = last;
+  		//handling empty bins
+  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
+  		RandomAccessIter lastFull = *local_bin;
+  		RandomAccessIter * target_bin;
+  		//Iterating over each element in the bin of empties
+  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  			//empties belong in this bin
+  			while(length(*current) > char_offset) {
+  				target_bin = end_bin - getchar((*current), char_offset);
+  				iter_swap(current, (*target_bin)++);
+  			}
+  		}
+  		*local_bin = nextbinstart;
+  		nextbinstart = first;
+  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+  		unsigned last_bin = max_bin;
+  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
+  		//This dominates runtime, mostly in the swap and bin lookups
+  		for(unsigned u = 0; u < last_bin; ++u) {
+  			local_bin = bins + u;
+  			nextbinstart += bin_sizes[u];
+  			//Iterating over each element in this bin
+  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+  				//Swapping elements in current into place until the correct element has been swapped in
+  				for(target_bin = end_bin - getchar((*current), char_offset);  target_bin != local_bin; 
+  					target_bin = end_bin - getchar((*current), char_offset))
+  					iter_swap(current, (*target_bin)++);
+  			}
+  			*local_bin = nextbinstart;
+  		}
+  		bins[last_bin] = lastFull;
+  		//Recursing
+  		RandomAccessIter lastPos = first;
+  		//Skip this loop for empties
+  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
+  			size_t count = bin_cache[u] - lastPos;
+  			//don't sort unless there are at least two items to compare
+  			if(count < 2)
+  				continue;
+  			//using std::sort if its worst-case is better
+  			if(count < max_size)
+  				std::sort(lastPos, bin_cache[u], comp);
+  			else
+  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
+  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
+  		}
+  	}
+
+  	//Holds the bin vector and makes the initial recursive call
+  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
+  	inline void 
+  	string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
+  	{
+  		std::vector<size_t> bin_sizes;
+  		std::vector<RandomAccessIter> bin_cache;
+  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
+  	}
+
+  	//Holds the bin vector and makes the initial recursive call
+  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
+  	inline void 
+  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
+  	{
+  		std::vector<size_t> bin_sizes;
+  		std::vector<RandomAccessIter> bin_cache;
+  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
+  	}
+
+  	//Holds the bin vector and makes the initial recursive call
+  	template <class RandomAccessIter, class get_char, class get_length, class data_type, class unsignedchar_type>
+  	inline void 
+  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, data_type, unsignedchar_type)
+  	{
+  		std::vector<size_t> bin_sizes;
+  		std::vector<RandomAccessIter> bin_cache;
+  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length);
+  	}
+
+  	//Holds the bin vector and makes the initial recursive call
+  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
+  	inline void 
+  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
+  	{
+  		std::vector<size_t> bin_sizes;
+  		std::vector<RandomAccessIter> bin_cache;
+  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
+  	}
+
+  	//Holds the bin vector and makes the initial recursive call
+  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
+  	inline void 
+  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
+  	{
+  		std::vector<size_t> bin_sizes;
+  		std::vector<RandomAccessIter> bin_cache;
+  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
+  	}
+  }
+
+  //Allows character-type overloads
+  template <class RandomAccessIter, class unsignedchar_type>
+  inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsignedchar_type unused) 
+  {
+  	//Don't sort if it's too small to optimize
+  	if(last - first < detail::MIN_SORT_SIZE)
+  		std::sort(first, last);
+  	else
+  		detail::string_sort(first, last, *first, unused);
+  }
+
+  //Top-level sorting call; wraps using default of unsigned char
+  template <class RandomAccessIter>
+  inline void string_sort(RandomAccessIter first, RandomAccessIter last) 
+  {
+  	unsigned char unused = '\0';
+  	string_sort(first, last, unused);
+  }
+
+  //Allows character-type overloads
+  template <class RandomAccessIter, class compare, class unsignedchar_type>
+  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused) 
+  {
+  	//Don't sort if it's too small to optimize
+  	if(last - first < detail::MIN_SORT_SIZE)
+  		std::sort(first, last, comp);
+  	else
+  		detail::reverse_string_sort(first, last, *first, unused);
+  }
+
+  //Top-level sorting call; wraps using default of unsigned char
+  template <class RandomAccessIter, class compare>
+  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp) 
+  {
+  	unsigned char unused = '\0';
+  	reverse_string_sort(first, last, comp, unused);
+  }
+
+  template <class RandomAccessIter, class get_char, class get_length>
+  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length) 
+  {
+  	//Don't sort if it's too small to optimize
+  	if(last - first < detail::MIN_SORT_SIZE)
+  		std::sort(first, last);
+  	else {
+  		//skipping past empties at the beginning, which allows us to get the character type 
+  		//.empty() is not used so as not to require a user declaration of it
+  		while(!length(*first)) {
+  			if(++first == last)
+  				return;
+  		}
+  		detail::string_sort(first, last, getchar, length, *first, getchar((*first), 0));
+  	}
+  }
+
+  template <class RandomAccessIter, class get_char, class get_length, class compare>
+  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 
+  {
+  	//Don't sort if it's too small to optimize
+  	if(last - first < detail::MIN_SORT_SIZE)
+  		std::sort(first, last, comp);
+  	else {
+  		//skipping past empties at the beginning, which allows us to get the character type 
+  		//.empty() is not used so as not to require a user declaration of it
+  		while(!length(*first)) {
+  			if(++first == last)
+  				return;
+  		}
+  		detail::string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
+  	}
+  }
+
+  template <class RandomAccessIter, class get_char, class get_length, class compare>
+  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 
+  {
+  	//Don't sort if it's too small to optimize
+  	if(last - first < detail::MIN_SORT_SIZE)
+  		std::sort(first, last, comp);
+  	else {
+  		//skipping past empties at the beginning, which allows us to get the character type 
+  		//.empty() is not used so as not to require a user declaration of it
+  		while(!length(*(--last))) {
+  			//Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order
+  			if(first == last)
+  				return;
+  		}
+  		//making last just after the end of the non-empty part of the array
+  		++last;
+  		detail::reverse_string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
+  	}
+  }
+}
+
+#endif