Sorting an array based on another array's order, quickly [closed]

Question

There are two arrays of maps. The first array contains maps of ID values in a specific order (but not necessarily either pure ASC or DESC ordering):

// pseudo code
first := [
    {"id": 1},
    {"id": 2},
    {"id": 3}
]

...and an unsorted array of data with corresponding ID values, but not in the same ordering:

second := [
    {"id": 3, "text": "hello"},
    {"id": 1, "text": "fizz"},
    {"id": 2, "text": "bar"}
]

How can I sort the second array such that its maps are in the same order as the first array via the matching ID values, while achieving the fastest code execution as possible?

(Note that the ordering of the first array is not known before runtime.)

The desired result in this case would be:

desiredResult := [
    {"id": 1, "text": "fizz"},
    {"id": 2, "text": "bar"},
    {"id": 3, "text": "hello"}
]

Answer 1

I'm going to assume that in the general case these ids might be strings and might be in a non-natural order in both first and second, since otherwise the trivial solutions suggested in the comments would be adequate.

One obvious solution is to walk through the lists linearly, rearranging the second array's elements along the way.

I assume this means that for each element in first, you do a linear search in second for the corresponding element and then insert it into the right position in result. This would be an O(n^2) algorithm.

I believe you can do this in O(n) by converting first into a map from id to index. So, assuming we start with this (I'll write Javascript since I'm better at that language, but I assume this works in Go too):

var first = [
  { "id": "biz" },
  { "id": "qux" },
  { "id": "foo" }
]

var second = [
  { "id": "foo", "text": "dabra" },
  { "id": "biz", "text": "abra" },
  { "id": "qux", "text": "ca" }
]

I would iterate over first to construct this map from ids to positions in the final array:

var idToPositionMap = {
  "biz": 0,
  "qux": 1,
  "foo": 2
}

Then I would iterate over second, using lookups in that map to insert items into the the result array:

second.map(function(item) {
   result[idToPositionMap[item.id]] = item;
});

Both of these steps should be O(n), assuming keyed lookup is O(1) and iterating over an array is O(n), like they should be, so total time is O(2n) = O(n).

I'm fairly sure O(n) is the best time complexity you can possibly get for this operation, since you need to touch every element of each array, so any further optimization would have to involve language-specific details and probably a lot of profiling.