sistemas de ordenacion

[vib]

Hola a todos de nuevo!
Abro el hilo viendo que con este tema no hay nada relacionado.

Acabe por fin mi motorcillo 2d para empezar hacer mis proyectos de juegos de forma ordenada y mas rapida...
La cosa es que ahora ordenando el codigo del motorcillo, he visto cosas que se pueden optimizar y me surgio la siguiente pregunta:

Para los videojuegos, cual es el mejor sistema de ordenacion?
Vale es una pregunta algo extensa y poco definida, me explico.
Tengo un sistema de ordenacion para controlar lo que se va a imprimir por pantalla...por capas " lo comente hace tiempo"
1r ordena, luego imprime.
1r ordena los de capa0, segun si la y es mayor o menor... luego capa1 etc
La cosa esque del programa es la parte que mas recursos y gasto genera y habia pensando reducirla a ser posible.

Ahora mismo, mi sistema de ordenacion es Mermeshort, lo que tengo fallo de codigo y en memoria se me va guardando todos las repeticiones, generandome una cantidad enorme de memoria que no es buena.

POR eso comentaba esto haber si podeis ayudarme en elegir el sistema adecuado.

Puntos a tener en cuenta:

El vector como mucho tendra unos 500 elementos, "por poner un numero" , los tiles del mapa y los elementos, objetos a mostrar.
el mapa estara ya ordenado, casi siempre
Los objetos no estaran ordenados
osea pongamos que necesito un sistema de ordecion para vectores pequeños..pero que si meto mas cantidad "500 o 1000" que tambien lo ordene con rapidez.

Yo elegi mermeshort porque es estable y rapidismo log n, pero al usar arrays auxiliares la memoria se me dispara, aparte de ese error de codigo que debo tener.

Aceptu sugerencias,
Mil gracias!

[IDandT]

Por Mermeshort, entiendo que te refieres a merge sort (ordenacion por mezcla).

Si es asi, mirando un poco he visto que por ejemplo quicksort suele ser mas rapido que mergesort, y creo que reduciria el problema de la memoria. Cosillas que he leido comparando ambos:

Most implementations of Mergesort, require additional scratch space, which could bash the performance. The pros of Mergesort are: it is a stable sort, and there is no worst-case scenario.

Quicksort is often implemented inplace thus saving the performance and memory by not creating extra storage space. However the performance falls on already sorted/almost sorted lists if the pivot is not randomized.

[vib]

Elegi merme sort en vez de quick sort por el tema que es estable y el caso mas malo es mucho mejor que quick sort.

   Merge sort    O(n log n) ..... y es estable
   Quicksort    Promedio: O(n log n),
                       peor caso: O(n²)                        y no es estable.

Claro mi vector generalmente estara bastante ordenada y usando quicksort ara casi siempre el peor caso...

Buscando se que hay muchisimos algoritmos de ordenacion, por eso me gustaria saber cual es para videojuegos el o los mas recomendados. :D