Sort an array by the contents of another in JavaScript

Question

Say I have an array of Person objects:

var people = [{name: "Joe Schmo", age: 36}, {name: "JANE DOE", age: 40}];

and I have a function which can sort an array of strings case insensitively:

function caseInsensitiveSort(arr) { ... }

Is there any straightforward way to combine my existing sort function with Array.prototype.map to sort the people array just using the name key?

I.e. it would produce

var people = [{name: "JANE DOE", age: 40}, {name: "Joe Schmo", age: 36}];

Doing it by hand is not hard in this particular case,

people.sort(function (a, b) {
    return a.name.localeCompare(b.name);
});

but I can't think of a way of doing it that would allow me to use the pre-existing sort function. In a case where the sort function is more customized, that would be useful.

Edit: I believe that the core problem here is that to do this well, you need to be able to figure out what the original indices were mapped to when you sort the proxy array. Getting those new indices using JS's native sort function does not seem possible in the general case. But I'd be happy to be proven wrong.

Edit: The way I was trying to do this is too inefficient to be useful. See the answer below for the solution using a comparison function instead.

If caseInsensitiveSort accepts an array, you would need to pass an array of the names to that function, sort the names, and then sort the array with the objects based on the array with the names. Sounds like a really complicated way to do something simple. — adeneo
– adeneo, Commented Apr 17, 2015 at 16:15
Does it will handle few elements? Because the Array.prototype.map method creates a new array, so with millions of records the best option is to sort it in-place. — Jordan Cortes
– Jordan Cortes, Commented Apr 17, 2015 at 16:17
@adeneo @Jordan You are both correct. As xdazz pointed out below, the correct way to do this efficiently is to abstract the logic of my comparison into a separate function, and provide that to Array.prototype.sort, rather than trying to wedge my sort function in. — Chris Middleton
– Chris Middleton, Commented Apr 17, 2015 at 16:19

Chris Middleton · Accepted Answer · 2015-04-17 17:14:41Z

4

You could use your existing function to get a sorted names array, then sort the people array by comparing the index in the sorted names array.

var names = caseInsensitiveSort(people.map(function(person) { 
    return person.name;
}));

people.sort(function (a, b) {
    return names.indexOf(a.name) - names.indexOf(b.name);
});

But this is not efficient, you should try to abstract out the compare logic from the caseInsensitiveSort function into a caseInsensitiveCompare function.

Then your example would become:

people.sort(function (a, b) {
    return caseInsensitiveCompare(a.name, b.name);
});

edited Apr 17, 2015 at 17:14

Chris Middleton

6,0225 gold badges39 silver badges71 bronze badges

answered Apr 17, 2015 at 16:12

xdazz

161k38 gold badges255 silver badges278 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Chris Middleton Over a year ago

The use of indexOf twice per sort iteration would make this pretty slow for a big array, but it's probably the only possible way of doing it in a general way. +1.

xdazz Over a year ago

@ChrisMiddleton Can't you abstract the compare logic from the caseInsensitiveSort function?

Chris Middleton Over a year ago

Yes, you're right. That's the real answer I think. To do this in a general and efficient way, you need to work at the level of the compare function, not the sort function. Thanks.

Chris Middleton Over a year ago

You should add a comment about doing it with a compare function instead to your answer for any future readers - the way I was trying to do this is fundamentally wrong.

JLRishe Over a year ago

This is, at best, an O(n^2 log^2 n) operation. Please don't do this.

JLRishe · Accepted Answer · 2015-04-17 16:29:38Z

1

Depending on how your caseInsensitiveSort() function works, you could make use of a .toString() method to do this:

var toSort = people.map(function (person) {
    return {
        person: person,
        toString: function () {
            return person.name;
        }
    };
});

caseInsensitiveSort(toSort);

people = toSort.map(function (item) { return item.person; });

If that is not an option, a messier yet still efficient approach is to sort the names, map them to their indices, and then sort based on that:

var names = people.map(function (person) { return person.name; });

caseInsensitiveSort(names);

var nameMap = {};
names.forEach(function (name, i) { 
    nameMap[name] = i;
});

people.sort(function (a, b) {
    return nameMap[a.name] - nameMap[b.name];
});

answered Apr 17, 2015 at 16:29

JLRishe

102k19 gold badges138 silver badges171 bronze badges

2 Comments

Chris Middleton Over a year ago

Thanks for adding this - your second solution is similar to what I was thinking when I asked. It of course only works if the values you are sorting are keyable values, but this is probably an unavoidable limitation, unless you used hash values for non-keyable values.

JLRishe Over a year ago

@ChrisMiddleton Yes, that's certainly true. It works for names, but wouldn't work for all types of values.

Collectives™ on Stack Overflow

Sort an array by the contents of another in JavaScript

2 Answers 2

5 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related