Performant Sort function for big arrays In sort(arr), I want to sort an array. Children must be beneath their parent. And children of the same parent are sorted using orderPos value.
I guess the complexity of this algorithm is quite high, is there a way to make it more performant for very long lists?
(the language used here is typescript)
     interface data { id:number; parentPK:number; orderPos:string; children: data[] }

 function sort(arr:data[]) {  const sorted : data[] = []; 
  let parent: data = {children: [] , id : 0 , orderPos:'0' , parentPK:0} ;   let i = 1;

  // detect parent of all , parent pk is -1 , assumes theres only one root element whose parent id is -1 
    arr.forEach(x =&gt; {
    
    if (x.parentPK == -1) {
      parent = x;
      sorted.push(x);
      arr.splice(arr.indexOf(x), 1);
      return;
    }   });   // root element is now first in the array   // get root's children and place them beneath their parent (sorted by orderPos)   

  let temp: data[] = arr
    .filter(x =&gt; x.parentPK === (parent &amp;&amp; parent.id))
    .sort((a, b) =&gt; parseInt(a.orderPos, 10) - parseInt(b.orderPos, 10));   sorted.push(...temp);   temp.forEach(x =&gt; parent.children.push(x));   while (i &lt; arr.length - 1) {
    // new parent
    parent = sorted[sorted.indexOf(parent) + 1];
    // place children beneath parent
    temp = arr.filter(x =&gt; x.parentPK === (parent &amp;&amp; parent.id)).sort((a, b) =&gt; parseInt(a.orderPos, 10) - parseInt(b.orderPos, 10));
    temp.forEach(x =&gt; parent.children.push(x));
    sorted.splice(sorted.indexOf(parent) + 1, 0, ...temp);
    i++;   }

  return sorted; }
  
  let array : data[] =  [ { id: 4, parentPK : 1, orderPos:'100' , children:[]}, {id:1, parentPK : -1, orderPos:'1', children:[] }, { id:2, parentPK : 1, orderPos:'51',children:[] }, {id:3, parentPK : 2, orderPos:'1',children:[] }, {id:5, parentPK : 2, orderPos:'10',children:[] } ] 
let sortedArray = sort(array)
console.log('sorted array : ',sortedArray.map(element =&gt; [element.id, element.parentPK,element.orderPos] ))
The main improvement that can be made in the algorithm is recognizing that you can reduce more expensive sorting (and make the algorithm a lot easier to understand at a glance) by arranging the data into a structure indexed by the parent ID first. This operation is O(n). (In contrast, sorting is O(n log n)) The data structure will look like:



// This is not runnable, I'm just using a snippet to hide this long code
const itemsByParentId = {
  // Key: parent ID
  "1": [
    // Value: Array of children which have that ID as a parent (parentPK)
  {
    "id": 4,
    "parentPK": 1,
    "orderPos": "100",
    "children": []
  }, {
    "id": 2,
    "parentPK": 1,
    "orderPos": "51",
    "children": []
  }],
  "2": [{
    "id": 3,
    "parentPK": 2,
    "orderPos": "1",
    "children": []
  }, {
    "id": 5,
    "parentPK": 2,
    "orderPos": "10",
    "children": []
  }],
  "-1": [{
    "id": 1,
    "parentPK": -1,
    "orderPos": "1",
    "children": []
  }]
}



Then:

For each subarray (where all elements with the same parent are grouped together), sort it by orderPos (there's no getting around the O(n log n) complexity here)

Make a function that, given a parent, finds child elements in the data structure with that parent ID (O(1)), pushes them to the output array (O(n)), and recursively iterates over its children, depth-first, as the algorithm requires.


function sort(arr: data[]) {
  const itemsByParentId: {
    [id: number]: Array&lt;data&gt;;
  } = {};
  // (1) Group by parent ID
  for (const item of arr) {
    if (!itemsByParentId[item.parentPK]) {
      itemsByParentId[item.parentPK] = [];
    }
    itemsByParentId[item.parentPK].push(item);
  }
  // (2) Sort each subarray
  for (const childrenArr of Object.values(itemsByParentId)) {
    childrenArr.sort((a, b) =&gt; Number(a.orderPos) - Number(b.orderPos));
  }
  // (3) Recursively add parents and their children, depth-first
  const sorted: data[] = [];
  const addParent = (parent: data) =&gt; {
    sorted.push(parent);
    if (!itemsByParentId[parent.id]) {
      return;
    }
    for (const child of itemsByParentId[parent.id]) {
      parent.children.push(child);
      addParent(child)
    }
  };
  addParent(itemsByParentId[-1][0]);
  return sorted;
}

Live snippet of the compiled code:


function sort(arr) {
    const itemsByParentId = {};
    for (const item of arr) {
        if (!itemsByParentId[item.parentPK]) {
            itemsByParentId[item.parentPK] = [];
        }
        itemsByParentId[item.parentPK].push(item);
    }
    for (const childrenArr of Object.values(itemsByParentId)) {
        childrenArr.sort((a, b) =&gt; Number(a.orderPos) - Number(b.orderPos));
    }
    const sorted = [];
    const addParent = (parent) =&gt; {
        sorted.push(parent);
        if (!itemsByParentId[parent.id]) {
            return;
        }
        for (const child of itemsByParentId[parent.id]) {
                parent.children.push(child);
            addParent(child);
        }
    };
    addParent(itemsByParentId[-1][0]);
    return sorted;
}
let array = [{ id: 4, parentPK: 1, orderPos: '100', children: [] }, { id: 1, parentPK: -1, orderPos: '1', children: [] }, { id: 2, parentPK: 1, orderPos: '51', children: [] }, { id: 3, parentPK: 2, orderPos: '1', children: [] }, { id: 5, parentPK: 2, orderPos: '10', children: [] }];
let sortedArray = sort(array);

console.log('sorted array : ',sortedArray.map(element =&gt; [element.id, element.parentPK,element.orderPos] ))



For a review of your existing code:
Put each statement on its own line, usually - this significantly improves readability and means that readers of the code don't have to scroll horizontally.
Indent when starting a new block, and indent when chaining methods off an expression above - for similar reasons to above, it makes it a lot easier to pick up on the logic at a glance. (Also use the same indentation across the same block.) There are many IDEs which will automatically format your code to adhere to some sort of standard like this. They're well worth using.
parentPK? Currently, an object's parentPK value links to another object's id value. I'm not sure what these objects represent in your wider script, but you might consider if it would be clearer if the parentPK property was named parentID or idOfParent instead, to make the link clearer.
Declare variables close to where they'll be used, to reduce cognitive overhead. For example, rather than:
let parent;
let i = 1;
// many lines of code that doesn't reference i
while (i &lt; arr.length - 1) {

you'll usually want to do
let parent;
// many lines of code that doesn't reference i
let i = 1;
while (i &lt; arr.length - 1) {

You could also consider a for loop, since you increment i at the end:
for (let i = 1; i &lt; arr.length - 1; i++) {

Use strict equality with === and !== - avoid != and ==, since they have strange coercion rules a reader of the script should not have to have memorized in order to understand the logic.
return does nothing in a forEach callback except terminate the current callback. It doesn't stop further callbacks from running. If you want to find the index of an element with a particular property in an array, use findIndex:
const rootIndex = arr.findIndex(item =&gt; item.parentPK === 1);
sorted.push(arr[rootIndex]);
arr.splice(rootIndex, 1);

Unnecessary comparison? I think parent will always exist, so the .filter(x =&gt; x.parentPK === (parent &amp;&amp; parent.id)) check of parent first is superfluous. (If it might not exist, then you could simplify with optional chaining: x.parentPK === parent?.id)