I don't think your code produces a result that is giving precedence to queuedAt when it should. Your algorithm first orders by queuedAt and then swaps elements that appear in the wrong position-order, but this does always not lead to an order that gives priority to queuedAt when possible.
For instance, in your output, the element with queuedAt=3 appears after the element with queuedAt=2, yet there is no reason why they could not have appeared in opposite order: that adapted ordering would still list items in their position-order when they belong to the same queue, but would give precedence to a greater queuedAt value.
Suggested Algorithm
To correct this shortcoming, and to get a better time complexity, you could use a max heap. One entry in this heap would correspond to a queue with all its elements ordered by position. The key to be used by the heap would be the queuedAt property of the queue's first element, i.e. the one with the least position value.
Then you would pick the top entry (queue) from the heap, extract the first element from that queue, and push it to the final result. If the queue is not yet empty, then leave it on the heap, but adapt its key, so it corresponds again to the queuedAt property of the queue element that now comes first (least position). If the queue is depleted, then remove it from the heap. If you continue like that until the heap is emptied, you'll have visited the entries in the desired order.
Unfortunately, JavaScript has no native heap implementation. So you'll have to throw your own, or include a library (there are several). I will include here the minified version of the implementation I posted in answer to Efficient way to implement Priority Queue in Javascript?. See there for an explanation of that code.
In the implementation below I have chosen to order the queues in reverse order, so I can pop the elements in the desired order.
Here we go:
/* MinHeap minimised - taken from https://stackoverflow.com/a/66511107/5459839 */
const MaxHeap={siftDown(h,i=0,v=h[i]){if(i<h.length){let k=v[0];while(1){let j=i*2+1;if(j+1<h.length&&h[j][0]<h[j+1][0])j++;if(j>=h.length||k>=h[j][0])break;h[i]=h[j];i=j;}h[i]=v}},heapify(h){for(let i=h.length>>1;i--;)this.siftDown(h,i);return h},pop(h){return this.exchange(h,h.pop())},exchange(h,v){if(!h.length)return v;let w=h[0];this.siftDown(h,0,v);return w},push(h,v){let k=v[0],i=h.length,j;while((j=(i-1)>>1)>=0&&k>h[j][0]){h[i]=h[j];i=j}h[i]=v;return h}};
// Main function
function customSort(data) {
// Create a map with a key for each queue
let map = new Map(data.map(o => [o.queueName, []]));
// Populate the map entries
for (let o of data) map.get(o.queueName).push(o);
// We have no more need of the Map:
let queues = [...map.values()];
// Sort each queue by descending position (so we can pop from those queues in ascending order)
for (let queue of queues) queue.sort((a, b) => b.position - a.position);
// Build a heap of pairs, where first value in pair is the heap key, and the second is the payload (the queue)
let heap = MaxHeap.heapify(queues.map(queue => [queue[queue.length - 1].enqueuedAt, queue]));
let result = [];
while (heap.length) {
// Peek in the heap, to get the "top" queue
let queue = heap[0][1];
// Extract the element from that queue with the lowest position
result.push(queue.pop());
if (queue.length) {
// Adapt the key of this queue on the heap
MaxHeap.exchange(heap, [queue[queue.length - 1].enqueuedAt, queue]);
} else {
// Remove the now empty queue from the heap
MaxHeap.pop(heap);
}
}
return result;
}
// Example data from the question:
const data = [{id: 1,enqueuedAt: 8,queueName: 'Queue 1',position: 1},{id: 2,enqueuedAt: 7,queueName: 'Queue 2',position: 1},{id: 3,enqueuedAt: 6,queueName: 'Queue 3',position: 3},{id: 4,enqueuedAt: 5,queueName: 'Queue 4',position: 2},{id: 5,enqueuedAt: 1,queueName: 'Queue 1',position: 2},{id: 6,enqueuedAt: 2,queueName: 'Queue 4',position: 1},{id: 7,enqueuedAt: 4,queueName: 'Queue 1',position: 3},{id: 8,enqueuedAt: 3,queueName: 'Queue 2',position: 2}]
console.log(customSort(data));
The time complexity is O(nlogn), like a normal comparison-based sort
A solution without heap
It is possible to get this working in JavaScript without the use of the heap, but it requires that requiredAt is limited in range (but it's still a large range: 232): We can make use of the key iteration order that JavaScript guarantees on plain objects since the 2017-2020 updates of the language specification.
Where requiredAt was the key in the heap, it can become the key in a plain object. As you need the order to be descending we must apply a mapping of requiredAt to positive integers that can be iterated in ascending order. The mapping can be something like: 32000 - requiredAt.
Here is how that can be coded:
function customSort(data) {
// Create a map with a key for each queue
let map = new Map(data.map(o => [o.queueName, []]));
// Populate the map entries
for (let o of data) map.get(o.queueName).push(o);
// We have no more need of the Map:
let queues = [...map.values()];
// Sort each queue by descending position (so we can pop from those queues in ascending order)
for (let queue of queues) queue.sort((a, b) => b.position - a.position);
// Build an object keyed by "negative" `queuedAt`
const MAX = 2 ** 31 - 1;
let sorted = Object.fromEntries(queues.map(queue => [MAX - queue[queue.length - 1].enqueuedAt, queue]));
let result = [];
for (let i = 0; i < data.length; i++) {
// Use JS behaviour where index keys are iterated in numerical order
let queuedAt;
for (queuedAt in sorted) break;
// Get the queue at this (first) key and remove the entry
let queue = sorted[queuedAt];
delete sorted[queuedAt];
// Extract the element from that queue with the lowest position
result.push(queue.pop());
if (queue.length) {
// Store the shortened queue at its new key
sorted[MAX - queue[queue.length - 1].enqueuedAt] = queue;
}
}
return result;
}
// Example data from the question:
const data = [{id: 1,enqueuedAt: 8,queueName: 'Queue 1',position: 1},{id: 2,enqueuedAt: 7,queueName: 'Queue 2',position: 1},{id: 3,enqueuedAt: 6,queueName: 'Queue 3',position: 3},{id: 4,enqueuedAt: 5,queueName: 'Queue 4',position: 2},{id: 5,enqueuedAt: 1,queueName: 'Queue 1',position: 2},{id: 6,enqueuedAt: 2,queueName: 'Queue 4',position: 1},{id: 7,enqueuedAt: 4,queueName: 'Queue 1',position: 3},{id: 8,enqueuedAt: 3,queueName: 'Queue 2',position: 2}]
console.log(customSort(data));
Final Remarks
Notice how the order is different from your output, but still is in line with the rules that you set out. The order in this solution really maximizes the priority of enqueuedAt.
