Сортировка отображения

[Nooob]

Для такой задачи лучше всего подходит сортировка вставками.
Потому что:
1. Высокая скорость на практически отсортированном массиве
2. Сохраняется первоначальный порядок
Время выполнения в худшем случае O(n²), в твоем случае O(n) - O(n + n)

var n:int = objects.length;
for (var i:int = 1; i < n; i++)
{
	var base:DisplayObject = objects[i];
	for (var j:int = i - 1; j >= 0; j--)
	{
		var current:DisplayObject = objects[j];
		if (current.y > base.y)
		{
			objects[j + 1] = current;
			continue;
		}
		break;
	}
	objects[j + 1] = base;
}
for (i = 0; i < n; i++)
{
	current = objects[i];
	if(current.parent == this)
	{
		setChildIndex(current, i);
		continue;
	}
	addChildAt(current, i);
}

[Babylon]

Я бы сначала проиндексировал объекты. Отсортировал по индексам
А сами объекты расставил бы только после сортировки по индексам.

[expl]

Вроде как for each не обещает правильный порядок следования

Для массивов и векторов обещает
А для ключей динамических объектов и Dictionary - вообще никто не обещает

Время выполнения в худшем случае O(n²), в твоем случае O(n) - O(n + n)

Я бы так смело оценки не занижал - нет уверенности, что setChildIndex отрабатывает за 1-ное время.

Хотя, на практике, обычно я видел похожие подходы, где двигается небольшое количество объектов на фоне сотен статичных.
Перемещаются они не на много - и в итоге срабатывает даже не O(n)(что было бы много), а 0-2 шага на персонажа
(хотя там так же не понятно, на сколько портит картину неединичная сложность работы AddChildAt, SetChildIndex и т.п.)
Но там промежуточный массив полностью не прогонялся ни в коем разе, просто при перемещении объекта смотрели, куда его переместить (выше или ниже) и искали место вставки в этом направлении - получалось мало шагов. При добавлении нового или при создании карты только большие нагрузки.

Это всё работало, если статичных объектов было на порядок больше динамических и они должны были участвовать в сортировке.