Sorting an array of objects by a property which may be missing

Question

Problem

I am sorting an array of objects. Each element may have a property called reference or it may be undefined. When defined, it is a user-provided string (which is why I use String.localeCompare()).

If the reference is not available, that element's relative position in the final list is irrelevant save that all blank references must appear grouped together at the end.

Implementation

function sort(searchResult) {
 const hasReference = searchResult
 .filter(taskCard => typeof taskCard.reference !== "undefined");
 const missingReference = searchResult
 .filter(taskCard => typeof taskCard.reference === "undefined");
 hasReference.sort(
 (tc1, tc2) => tc1.reference.localeCompare(tc2.reference)
 );
 return hasReference.concat(missingReference);
}

My Concerns

1. Is this an efficient way of solving this problem in terms of time?
2. I'm currently iterating over the initial array twice. Is there an elegant ES6 way to do this in a single pass that I'm not seeing?
3. I believe memory to be less of a concern (because I exactly double the amount of memory used while processing by generating two new arrays that together are the size of the original); am I correct?
4. Are there any scalability pitfalls doing it this way?
5. As usual, any other comments are welcome.

Answer 1

Is this an efficient way of solving this problem in terms of time?

The filtering steps have time complexity \$O(n)\,ドル and the sorting step has \$O(n \log n)\$. Even if the filtering may look a bit of a waste, the dominant operation is the sort, if most of the items have the reference property.

I'm currently iterating over the initial array twice. Is there an elegant ES6 way to do this in a single pass that I'm not seeing?

Yes, you could implement the compare method in a way that items with undefined value as the property get sorted at the end, as @igor-soloydenko did in his answer.

I believe memory to be less of a concern (because I exactly double the amount of memory used while processing by generating two new arrays that together are the size of the original); am I correct?

Extra \$O(n)\$ memory doesn't seem a big concern. If it is, then you can use the in-place alternative, that doesn't use extra memory. More or less, see the next point.

Are there any scalability pitfalls doing it this way?

The only scalability pitfall that I see is the extra \$O(n)\$ memory, in case of very large input.

The fact that you partition the input has the interesting effect that if a large portion of the input has undefined values, the sorting step will be faster using the current technique compared to the in-place alternative, because the items with undefined values will not be part of the slow sort operation. If you don't expect many undefined values, then the in-place technique should be faster.

• msanford: "the sorting step will be faster using the current technique compared to the in-place alternative in a previous point" this is part of the reason I split the input. In my test data a large portion is undefined; however, it remains to be seen if this will be the case in production.

Answer 2

Here's a single-pass example. Very similar to @janos' code (which has a good complexity analysis). The only difference is in how various cases with undefined are treated.

function sort(searchResult) {
 return searchResult.sort((tc1, tc2) => {
 const tc1RefUndefined = tc1.reference == null;
 const tc2RefUndefined = tc2.reference == null;
 if (tc1RefUndefined || tc2RefUndefined) {
 if (tc1RefUndefined && tc2RefUndefined) {
 return 0;
 // or if consistency in grouping (within the groups) is necessary:
 // return tc1.otherProperty comparedTo tc2.otherProperty
 } else if (tc1RefUndefined) {
 return -1;
 } else {
 return 1;
 }
 }
 return tc1.reference.localeCompare(tc2.reference);
 });
}

• Igor Soloydenko: @msanford this is true. Fixed now. I'd rather use const tc1RefUndefined = typeof tc1.reference == null; though, because in most (not all) cases null and undefined may be treated as the same thing. This detail is specific to a particular app implementation.
• Igor Soloydenko: I meant const tc1RefUndefined = tc1.reference == null; lol

Answer 3

A a bit more cryptic but shorter variation of the solution by @IgorSoloydenko could be:

function sort(searchResult) {
 return searchResult.sort((tc1, tc2) => {
 const tc1RefUndefined = tc1.reference == null ? 1 : 0;
 const tc2RefUndefined = tc2.reference == null ? 1 : 0;
 if (tc1RefUndefined || tc2RefUndefined) {
 return tc1RefUndefined - tc2RefUndefined;
 }
 return tc1.reference.localeCompare(tc2.reference);
 });
}

• Igor Soloydenko: If both tc1's and tc2's references are set to null/undefined, we get tc1RefUndefined == tc2RefUndefined == 0. The instructions under if (tc1RefUndefined || tc2RefUndefined) will not get executed therefore, which [I think] is a bug. Moreover, it will let the tc1.reference.localeCompare(tc2.reference) get executed, that will result in a "Can't get localeCompare of null/undefined".
• Igor Soloydenko: I think, you need to do const tc1RefUndefined = tc1.reference == null ? 1 : 0; and const tc2RefUndefined = tc2.reference == null ? 1 : 0; and then return tc2RefUndefined - tc1RefUndefined; maybe? I really like the commonly applied idea of subtracting numeric fields for comparison. The issue is that cryptic implementations are less readable and bug prone. This can be improved a bit with a good set of unit tests, but I don't know whether it worth it.
• RoToRa: Oops, yes, I accidently swapped the values. I've edited it. Thanks.