Рабочий пример приведенного ниже кода находится на jsFiddle.

Индексируйте дерево по идентификатору и просматривайте его вверх, от каждого узла, и считайте, пока не дойдете до корня. Сначала индексируя, мы приближаемся к временной сложности O (n) (в зависимости от плотности дерева). ****Обновлено, чтобы удовлетворить требования сортировки и разрешить исключение корневого узла***:

function levelAndSort(data, startingLevel) {
    // indexes
    var indexed = {};        // the original values
    var nodeIndex = {};      // tree nodes
    var i;
    for (i = 0; i < data.length; i++) {
        var id = data[i].id;
        var node = {
            id: id,
            level: startingLevel,
            children: [],
            sorted: false
        };
        indexed[id] = data[i];
        nodeIndex[id] = node;
    }

    // populate tree
    for (i = 0; i < data.length; i++) {
        var node = nodeIndex[data[i].id];
        var pNode = node;
        var j;
        var nextId = indexed[pNode.id].parentId;
        for (j = 0; nextId in nodeIndex; j++) {
            pNode = nodeIndex[nextId];
            if (j == 0) {
                pNode.children.push(node.id);
            }
            node.level++;
            nextId = indexed[pNode.id].parentId;
        }
    }

    // extract nodes and sort-by-level
    var nodes = [];
    for (var key in nodeIndex) {
        nodes.push(nodeIndex[key]);
    }
    nodes.sort(function(a, b) {
        return a.level - b.level;
    });

    // refine the sort: group-by-siblings
    var retval = [];
    for (i = 0; i < nodes.length; i++) {
        var node = nodes[i];
        var parentId = indexed[node.id].parentId;
        if (parentId in indexed) {
            var pNode = nodeIndex[parentId];
            var j;
            for (j = 0; j < pNode.children.length; j++) {
                var child = nodeIndex[pNode.children[j]];
                if (!child.sorted) {
                    indexed[child.id].level = child.level;
                    retval.push(indexed[child.id]);
                    child.sorted = true;
                }
            }
        }
        else if (!node.sorted) {
            indexed[node.id].level = node.level;
            retval.push(indexed[node.id]);
            node.sorted = true;
        }
    }
    return retval;
}

Пример:

// level 0 (root) excluded
var startingLevel = 1;
var someData = [
    {id : "id-1", parentId : "id-0"},
    {id : "id-2", parentId : "id-0"},
    {id : "id-3", parentId : "id-2"},
    {id : "id-4", parentId : "id-3"},
    {id : "id-5", parentId : "id-4"},
    {id : "id-6", parentId : "id-4"},
    {id : "id-7", parentId : "id-0"},
    {id : "id-8", parentId : "id-1"},
    {id : "id-9", parentId : "id-7"},
    {id : "id-10", parentId : "id-1"},
    {id : "id-11", parentId : "id-1"},
    {id : "id-12", parentId : "id-1"}
];
var outputArray = levelAndSort(someData, startingLevel);

Выход:

Примечание

Если вы измените порядок ввода, сортировка получится немного другой, но все равно правильной (т. е. в порядке уровней, сгруппированных по родственным элементам).

Я не уверен, где вы берете значение для level, поэтому я предполагаю, что это просто целое число. Кстати, вы можете добавить свойство уровня к каждому элементу вашего массива, перебирая его.

for (var i = 0, l = data.length; i < l; i++) { 
    data[i].level = i
}

что даст

data = [{id:"1", parentId:"3", level:0 }, {id:"2", parentId:"1", level:1 } ...]

Вот ваш рабочий код. Уровень начинается со 2.

ПРЕДУПРЕЖДЕНИЕ. Если уровень не может быть рассчитан, приложение может войти в бесконечный цикл. Итак, убедитесь, что parentId действителен для всех объектов и хотя бы у одного из них есть parentId="id-1".

<script type="text/javascript">
    data = [
        {
            id:"id-2",
            parentId:"id-3"
        },
        {
            id:"id-4",
            parentId:"id-2"
        },
        {
            id:"id-3",
            parentId:"id-5"
        },
        {
            id:"id-5",
            parentId:"id-1"
        }
    ];

    function processData() {
        flag = true;

        while(flag) {
            flag = false;

            for(var i = 0; i < data.length; i++) {
                if(data[i].parentId == "id-1") {
                    data[i].level = 2;
                } else {
                    l = getLevel(data[i].parentId);
                    if(l > 0) {
                        data[i].level = l + 1;
                    } else {
                        flag = true;
                    }
                }
            }
        }
    }

    function getLevel(id) {
        for(var i = 0; i < data.length; i++) {
            if(data[i].id == id) {
                if(data[i].level) {
                    return data[i].level;
                } else {
                    return 0;
                }
            }
        }

        return 0;
    }

    processData();

    console.log(data);

</script>

Один из способов решить эту проблему без необходимости рекурсии — создать иерархию DOM. Для каждого элемента в массиве создайте div и прикрепите его к его родителю. затем пройдитесь по DOM и назначьте уровни (сверху — уровень 1, затем добавьте 1 для каждого дочернего элемента).

Я создал примерную демонстрацию здесь: http://jsfiddle.net/4AqgM/.

Выдержка из кода:

top.dataset.level="1";
var topChildren=top.getElementsByTagName("div");
for (var i=0;i<topChildren.length;i++) {
topChildren[i].dataset.level=parseInt(topChildren[i].parentNode.dataset.level)+1;
}