You have to shift the array (move items) to keep it sorted, but take care of the index in actor for children if you use index there, if you use pointer, you will not have issue.

You can have a function in the scene manager which do the shift, you call it in actor when AddChild, the actor has a pointer of the scene.

Another approach is to use a root array and a linear array, the linear array is in a random order (the linear array is not sorted).

On this approach you also have two functions in the scene to remove or add an actor in the root array.

Using this approach you then update the scene using the root array recursively.

This isn't possible with your approach, right?

I don't see why.

but I also need to store AABBs for collision detection and culling. What do I do about that?

Put them in another array, and update that in the same update loop.

Also, a normal scene node hierarchy lets the user have many different types of scene nodes attached to one another to get diverse results. This isn't possible with your approach, right?

Don't implement different types of scene node. A scene node is just a transform, a parent pointer, and an AABB. Whatever else you need is a separate object which is attached to the scene node.

Whatever else you need is a separate object which is attached to the scene node.

In other words : components.