Sorting the tree recursively based on two properties

I have a tree like this:

var children = [
    {
        label: 'Foo',
        children: [ ... ]
    }
    ...
];

      

        
        
        
      

    

I need to sort it with two constraints:

• Nodes with children go first and are sorted within themselves
• Nodes without children enter the second and are sorted inside themselves

The number of children does not matter if it is greater than 0.

So, if the original tree is represented like this:

Foo.0
Sou.2
    Zorro.0
    Amba.0
Book.0
Bud.1
    Ram.0

      

        
        
        
      

    

When sorting it looks like this:

Bud.1
    Ram.0
Sou.2
    Amba.0
    Zorro.0
Book.0
Foo.0

      

        
        
        
      

    

So, I came up with two recursive solutions:

The first just applies the built-in sort function:

function sortFn(a, b) {
    var aHasChildren = a.children.length,
        bHasChildren = b.children.length;

    if (aHasChildren && bHasChildren || !aHasChildren && !bHasChildren) {
        return a.label.localeCompare(b.label);
    } else {
        return aHasChildren ? -1 : 1;
    }
}

function sortNodesAndChildren(nodes) {
    return nodes
        .sort(sortFn)
        .forEach(function (node) {
            if (node.children.length) {
                sortNodesAndChildren(node.children);
            }
        })
}

      

        
        
        
      

    

The second uses additional arrays, stored in sorted order, and inserts elements into those arrays using linear insertion sort:

function sort(nodes) {
    var a = [];
    var b = [];

    nodes.forEach(function (node) {
        if (node.children.length === 0) {
            insert(a, node);
        } else {
            insert(b, node);
            node.children = sort(node.children);
        }
    });

    return b.concat(a);
}


function insert(a, o, property) {
    for (var i = 0; i < a.length; i++) {
        if (o.label.localeCompare(a[i].label) === -1) {
            a.splice(i, 0, o);
            return;
        }
    }

    a.push(o);
}

      

        
        
        
      

    

The second implementation shows significantly worse results in jsperf. But I think they should be compared using complexity rather than performance. So I have two questions:

• Is the second implementation worse in terms of algorithmic complexity?
• Is there a better way to accomplish the task other than what I am facing?