How do I perform a merge sort based on the property of an object (rather than an Array)?

Question

Background

Using JavaScript, I need to sort a large JSON object based on a given property of that object. I am assuming that a merge sort is the fastest approach. If this is not the fastest approach, please tell me what is. There are myriad examples online of a merge sort against an array, but very little with objects. Here is a sample object:

fruitForSale = {
     1: {"type":"orange","UnitPrice":0.20},
     2: {"type":"banana","UnitPrice":0.30},
     3: {"type":"pear","UnitPrice":0.10},
     4: {"type":"apple","UnitPrice":0.50},
     5: {"type":"peach","UnitPrice":0.70}
}

Question

Using a merge sort (or faster algorithm), how would I sort the fruitForSale object so that I end up with an object sorted by 'type':

   fruitForSale = {
                     4: {"type":"apple","UnitPrice":0.50},
                     2: {"type":"banana","UnitPrice":0.30},
                     1: {"type":"orange","UnitPrice":0.20},
                     5: {"type":"peach","UnitPrice":0.70},
                     3: {"type":"pear","UnitPrice":0.10}                  
                   }

NOTE: The original keys (1,2,3,4 & 5) would need to stay assigned to their respective object, so a key of 1 should always match with {"type":"orange","UnitPrice":0.20} and a key of 2 will always match with {"type":"banana","UnitPrice":0.30} and so on.

Thanks!

You cannot sort object properties. You can create an array of keys or just create an array of objects. Then have a look at [Sort JavaScript array of Objects](http://stackoverflow.com/questions/5421253/sort-javascript-array-of-objects) or [similar questions](http://stackoverflow.com/search?q=sort+array+of+objects+by+field&submit=search). — Felix Kling, Apr 08 '12 at 20:01
in addition, Objects have no order (although they seem to have). This looks like an array to me, why complicate things by using objects instead? — David Hellsing, Apr 08 '12 at 20:48
@Felix: Couldn't he do `fruitForSale.sort(function(a, b) { return a.type - b.type; })` — playeren, Apr 08 '12 at 20:49
@David--I need the keys because I have used them to establish a relationship with another JSON object. Thanks. — Matt Cashatt, Apr 08 '12 at 21:06
You could do `fruitForSale.length = 5; [].sort.call(fruitForSale, function(a,b){ return a.type > b.type });` ... but it would destroy your keys. As others mentioned, object properties aren't ordered, so "sorting" them really makes no sense unless you mean re-numbering numeric keys. — Dagg Nabbit, Apr 08 '12 at 21:50
Why the down-vote after the question was asked and answered?? Drive-by?? — Matt Cashatt, Apr 09 '12 at 03:18

score 2 · Accepted Answer · edited May 23 '17 at 11:50

You can't sort the keys on the object, but you can keep your own array of sorted keys.

var fruitForSale = {
     1: {"type":"orange","UnitPrice":0.20},
     2: {"type":"banana","UnitPrice":0.30},
     3: {"type":"pear","UnitPrice":0.10},
     4: {"type":"apple","UnitPrice":0.50},
     5: {"type":"peach","UnitPrice":0.70}
},

sortedKeys = Object.keys(fruitForSale).sort(function (i,j) {
    return fruitForSale[i]["type"] > fruitForSale[j]["type"];
});

Example: http://jsfiddle.net/X2hFt/ (Output displayed on the console)

Object.keys is not supported everywhere but you can polyfill if you need to easily. See:

https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Object/keys

Oh, and if you are curious about the underlying implementation of sort see:

Javascript Array.sort implementation?

How do I perform a merge sort based on the property of an object (rather than an Array)?

Background

Question

1 Answers1