One pass of bubble sort has exactly two cache misses since it traverses the data set exactly once, and strictly linearly. At the second cache miss, the hardware prefetcher kicks in.
For random input, it has on the average n/2 branch mispredictions if the compiler doesn't optimize properly, and zero with a compiler that uses CMOV.
In any case, its amortized runtime is constant. You can call it "temporal coherence", if you think that sounds more intelligent, but it's the same thing.

Since you like to childishly mangle quotes, be glad Bregma caught the fact that you don’t know what a stable sort is rather than myself. I’d not have been so kind.

However you decided to keep going, and now you’re not just arguing with me but with Wikipedia:


http://en.wikipedia.org/wiki/Bubble_sort#In_practice

Bubble sort is asymptotically equivalent in running time to insertion sort in the worst case, but the two algorithms differ greatly in the number of swaps necessary. Experimental results such as those of Astrachan have also shown that insertion sort performs considerably better even on random lists. For these reasons many modern algorithm textbooks avoid using the bubble sort algorithm in favor of insertion sort.

Bubble sort also interacts poorly with modern CPU hardware. It requires at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions. Experiments by Astrachan sorting strings in Java show bubble sort to be roughly 5 times slower than insertion sort…

In any case, its amortized runtime is constant. You can call it "temporal coherence", if you think that sounds more intelligent, but it's the same thing.

No, they are not the same thing. An amortized constant run-time is the result of temporal coherence.

Frame-to-frame temporal coherence in the case of a render queue means using the sorted results from the previous frame to increase the performance of the sort on the current frame. By using temporal coherence you typically get the best case O(n) for both bubble sort and insertion sort, resulting in an amortized run-time constant.

Now the only question that remains is why you want to stick to a bubble sort so badly. It sounds as though you just want to argue by this point, especially by how you mangled my quote.

L. Spiro

Wow, thanks a lot for all the input (and entertainment : )

Now let's see how I can use all this information.

What I've done so far:

- make the vectors I use for sorting, members of my class, no stack allocation each time I sort

- decided now to use std::sort instead of std::stable_sort, the chances that two floats with the distance of renderable to camera are exactly the same, are minimal.

In the near future I'll get into radix sorting and see if I can learn this.

- decided to implement some sort of 'temporal coherency', assuming that this means that I will reuse the sort results of the last time, to save time on sorting in the next iteration

- cull and sort each 2 frames instead of each frame (not noticable till now)

Here's the code I have now, with some flaws:

/** definition of the sorting vectors, in my class **/

	// Sorting vectors
	std::vector<int>	mBlendSortIndexTemp;	
	std::vector<int>	mBlendSortOrderTemp;	
	std::vector<float>	mBlendSortDistToCam;	

/** initial setting up the renderqueue **/

	// Vectors for sorting, note: size = total nr. of blended renderables
	mBlendSortIndexTemp.resize(nrBlendedRend);
	mBlendSortOrderTemp.resize(nrBlendedRend);
	mBlendSortDistToCam.resize(nrBlendedRend);

	for(int init=0;init<nrBlendedRend;++init) mBlendSortOrderTemp[init] = init;

/** the sorting function, called after the mBlendedBucket is filled with visible renderables **/

/**************************************************************************************/
/***							SORT BUCKET BLENDED									***/
/*** ==> usage: sort blended renderables, after the bucket is refilled 				***/
/*** ==> updates the order for blended renderables, back to front on cam distance	***/
/**************************************************************************************/

bool CRenderQueue::SortBucketBlended()
{
	if(mEffectDataCreated)
	{
		size_t bucketSize = mBucketBlended.size();

		for(size_t renderable=0;renderable<bucketSize;++renderable)
		{
			mBlendSortOrderTemp[renderable] = renderable;		// needed because of 'varying' bucket
			mBlendSortIndexTemp[renderable] = renderable;
			mBlendSortDistToCam[renderable] = mBucketBlended[renderable].DistToCam;
		}

		sort(mBlendSortOrderTemp.begin(), mBlendSortOrderTemp.begin() + bucketSize, [&](int a, int b)
			{ return mBlendSortDistToCam[a] > mBlendSortDistToCam[b]; });
		// replace "mBlendSortOrderTemp.being() + bucketSize" by ".end()", works only if bucket size/content doesn't vary
		// OR resize the vectors each time sorting is done?!

		mBucketBlendedIndex.resize(bucketSize);

		for(size_t results=0;results<bucketSize;++results)
			mBucketBlendedIndex[results] = mBlendSortIndexTemp[mBlendSortOrderTemp[results]];
			
		return true;
	}
	else return false;
}

The 'flaws'/ challenges I face;

- my mBlendedBucket content varies each frame, it contains only visible renderables at that moment

- my current order of doing things is:

** cull all renderables

** save the visible ones in the mBlendedBucket

** sort the mBlendedBucket into new index, NO temporal coherency (sort order is reset to 0, 1, 2, 3 etc. each new sort I do)

** render using the new index (don't sort the bucket objects itself)

With this situation, I have some disavantages:

- I have to resize the vector and/or reset the tempOrder (0, 1, 2 etc.)

- this throws away the possibility of having temporal coherency (/reusing the order from the last sort)

I've thought how to solve this, but can only conclude that this would only be possible when I always sort ALL renderables, instead of sorting only the visible ones.
I would appreciate some pointers on how to achieve my goal without having to sort ALL renderables (and not continue of the discussion std::sort versus insertion versus radix).

Any input is welcome.

I've thought how to solve this, but can only conclude that this would only be possible when I always sort ALL renderables, instead of sorting only the visible ones.

** sort the mBlendedBucket into new index, NO temporal coherency (sort order is reset to 0, 1, 2, 3 etc. each new sort I do)

#1: Add render-queue items to a render queue.
- #a: If the total number of items is the same as in the last frame, continue.
- #b: If the total number of items is less than before, recreate the index list from 0 to total items, in order.
- #c: If the total number of items is greater than before, just add the new indices in order at the end of the list, not modifying the indices from the previous frame.

#ifndef __LSSTD_INDEXSORTER_H__
#define __LSSTD_INDEXSORTER_H__

#include "../LSSTDStandardLib.h"
#include "LSSTDSearch.h"

namespace lsstd {

	/**
	 * Class CIndexSorter
	 * \brief Sorts data by index references.
	 *
	 * Description: Sorts data by index references.  Instead of moving the actual data around, it creates an index table
	 *	for that data and sorts the indices.  This is often faster than trying to sort data composed of many-byte elements.
	 *	The data being sorted must provide < and == operators.
	 */
	template <typename _tType>
	class CIndexSorter {
	public :
		// == Various constructors.
		LSE_CALLCTOR							CIndexSorter() :
			m_pui32Indices( NULL ),
			m_ui32TotalIndices( 0UL ),
			m_ui32AllocIndices( 0UL ) {
		}
		LSE_CALLCTOR							~CIndexSorter() {
			delete [] m_pui32Indices;
		}


		// == Operators.
		/**
		 * Assignment operator.
		 *
		 * \param _isOther The object to copy.
		 * \return Returns the copied instance.
		 */
		CIndexSorter<_tType> & LSE_CALL			operator = ( const CIndexSorter<_tType> &_isOther ) {
			if ( _isOther.m_pui32Indices > m_pui32Indices ) {
				// Have to allocate more.
				delete [] m_pui32Indices;
				m_pui32Indices = new LSUINT32[_isOther.m_pui32Indices];
				m_ui32AllocIndices = _isOther.m_pui32Indices;
			}
			m_ui32TotalIndices = _isOther.m_pui32Indices;
			for ( LSUINT32 I = m_ui32TotalIndices; I--; ) {
				m_pui32Indices[I] = _isOther.m_pui32Indices[I];
			}
			return (*this);
		}


		// == Functions.
		/**
		 * Sort the given data using an insertion sort.
		 *
		 * \param _ptData The data to sort.
		 * \param _ui32Total Total objects to sort.
		 * \return Returns a reference to this object.
		 */
		CIndexSorter<_tType> & LSE_CALL			InsertionSort( const _tType * _ptData, LSUINT32 _ui32Total ) {
			PrepareFor( _ui32Total );
			if ( _ui32Total <= 1UL ) { return (*this); }	// 0 or 1 items cannot be sorted.

			// Sort it.
			InsertionSort( m_pui32Indices, _ptData, m_ui32TotalIndices );
			return (*this);
		}

		/**
		 * Gets a pointer to the (sorted) index data.
		 *
		 * \return Returns a pointer to the (sorted) index data.
		 */
		const LSUINT32 * LSE_CALL				GetIndices() const { return m_pui32Indices; }

		/**
		 * Prepares to sort the given number of elements, but does not sort them.
		 *
		 * \param PARM The number of elements to prepare to sort.
		 */
		LSVOID LSE_CALL							PrepareFor( LSUINT32 _ui32Total ) {
			if ( _ui32Total > m_ui32AllocIndices ) {
				// Up-size the allocated amount.
				delete [] m_pui32Indices;
				m_pui32Indices = new LSUINT32[_ui32Total];
				m_ui32AllocIndices = _ui32Total;
				m_ui32TotalIndices = 0UL;
			}
			if ( m_ui32TotalIndices > _ui32Total ) {
				for ( LSUINT32 I = 0UL; I < _ui32Total; ++I ) {
					// Add indices that were not added before.
					m_pui32Indices[I] = I;
				}
			}
			else {
				for ( LSUINT32 I = m_ui32TotalIndices; I < _ui32Total; ++I ) {
					// Add indices that were not added before.
					m_pui32Indices[I] = I;
				}
			}
			m_ui32TotalIndices = _ui32Total;
		}


	protected :
		// == Members.
		/**
		 * Sorted indices.
		 */
		LSUINT32 *								m_pui32Indices;

		/**
		 * Total indices.
		 */
		LSUINT32								m_ui32TotalIndices;

		/**
		 * Total indices allocated.
		 */
		LSUINT32								m_ui32AllocIndices;


		// == Functions.

		/**
		 * Use an insertion sort to sort the array of indices.
		 *
		 * \param _pui32Indices The indices to sort.
		 * \param _ptValues The values to sort in-place.
		 * \param _uiptrTotal Total elements to which _ptValues and _pui32Indices point.
		 */
		static LSVOID LSE_CALL					InsertionSort( LSUINT32 * _pui32Indices, const _tType * _ptValues, LSUINTPTR _uiptrTotal ) {
			if ( _uiptrTotal <= 1UL ) { return; }
			LSUINT32 * pui32Cur = _pui32Indices + 1UL;
			LSUINT32 * pui32End = _pui32Indices + _uiptrTotal;
			while ( pui32Cur < pui32End ) {
				const _tType * ptKey = &_ptValues[(*pui32Cur)];
				for ( LSUINT32 * pui32NextDown = pui32Cur - 1UL; pui32NextDown >= _pui32Indices && (*ptKey) < _ptValues[(*pui32NextDown)]; --pui32NextDown ) {
					LSUINT32 ui32Temp = (*pui32NextDown);
					(*pui32NextDown) = pui32NextDown[1];
					pui32NextDown[1] = ui32Temp;
				}
				++pui32Cur;
			}
		}
	};

}	// namespace lsstd

#endif	// __LSSTD_INDEXSORTER_H__

@LSpiro: thanks (again), I concluded this point a bit late after understanding it all.

I've done the changes and got it all working, see below.

I've written "possible optimization: blend sort, replace std::sort by radix sort" on my list of remarks in my code documentation.

This topic was quite something, but in the end I can say that I'm happpy with the result :)

Any left over feedback is appreciated.

/**************************************************************************************/
/***							SORT BUCKET BLENDED									***/
/*** ==> usage: sort blended renderables, after the bucket is refilled 				***/
/*** ==> updates the order for blended renderables, back to front on cam distance	***/
/**************************************************************************************/

bool CRenderQueue::SortBucketBlended()
{
	if(mEffectDataCreated)
	{
		size_t bucketSize = mBucketBlended.size();
		size_t lastBucketSize = mBlendSortOrderTemp.size();

		// Scenario 1: new bucket size == last bucket:		don't change reference 'OrderTemp'
		// Scenario 2: new bucket size < then last bucket	refill 'OrderTemp' (invalid objects!)
		if(bucketSize < lastBucketSize)
		{
			mBlendSortOrderTemp.resize(bucketSize);
			for(size_t r=0;r<bucketSize;++r) mBlendSortOrderTemp[r] = r;
		}
		// Scenario 3: new bucket size > then last bucket	add indices to 'OrderTemp' to match bucket Size
		if(bucketSize > lastBucketSize)
		{
			for(size_t r = lastBucketSize;r<bucketSize;++r) mBlendSortOrderTemp.push_back(r);
		}

		for(size_t renderable=0;renderable<bucketSize;++renderable)
		{
			mBlendSortIndexTemp[renderable] = renderable;
			mBlendSortDistToCam[renderable] = mBucketBlended[renderable].DistToCam;
		}

		sort(mBlendSortOrderTemp.begin(), mBlendSortOrderTemp.end(), [&](int a, int b)
			{ return mBlendSortDistToCam[a] > mBlendSortDistToCam[b]; });

		// copy results to the new index
		if(bucketSize != lastBucketSize) mBucketBlendedIndex.resize(bucketSize);
		for(size_t results=0;results<bucketSize;++results)
			mBucketBlendedIndex[results] = mBlendSortIndexTemp[mBlendSortOrderTemp[results]];
			
		return true;
	}
	else return false;
}