Post History

> _**PS**: for small arrays and/or if the function is fast and doesn't cause performance bottlenecks, none of the below is really necessary (see the analysis in the end). That said, let's see how to solve it._

I'm going to suggest two ways to make sure that the `getSortKey` function processes each element just once: [memoization](https://en.wikipedia.org/wiki/Memoization) and [Schwartzian Transform](https://en.wikipedia.org/wiki/Schwartzian_transform).

---

# Memoization

The idea of memoization is to store the already computed results, and if the function is called with the same arguments, we return this pre-computed value, instead of calculating it again (and that's exactly what we need, to avoid the value to be processed again). One way to do it:

```javascript
var computed = {};
function getSortKeyMem(item) {
    if (!computed[item]) {
        console.log('getSortKey', item); // log only when processing the value
        computed[item] = parseInt(item);
    }
    return computed[item];
}

let array = ['4', '16', '8', '2', '6'];
array.sort((a, b) => getSortKeyMem(a) - getSortKeyMem(b));
console.log(array);
```

The output is:

```none
getSortKey 16
getSortKey 4
getSortKey 8
getSortKey 2
getSortKey 6
[ '2', '4', '6', '8', '16' ]
```

Now, each element was processed just once. When the function was called again, it used the pre-computed value.

> Of course [there are more sophisticated ways to do it](https://dev.to/anishkumar/memoizing-fetch-api-calls-in-javascript-1d16), but I'm not focusing on "*the best way to implement memoization*". I'm just showing that if you use it, each element is processed only once.

---

# Schwartzian Transform

The [Schwartzian Transform](https://en.wikipedia.org/wiki/Schwartzian_transform) is inspired by Lisp's *decorate-sort-undecorate* pattern.

It basically consists on computing the function value for all elements, and put the results in the array (or generate another, temporary one) - that's the decorate step. Then, sort the elements, using the computed values (the sort step). Finally, remove the computed values (undecorate step), and you'll have the original elements sorted.

Using the same function above (but without memoization), and applying the Schwartzian transform:

```javascript
function getSortKey(item) {
    console.log('getSortKey', item);
    return parseInt(item);
}

const array = ['4', '16', '8', '2', '6'];

// decorate: computes the key for each element and store it in the array
for (let i = 0; i < array.length; i++) {
    array[i] = [ array[i], getSortKey(array[i]) ];
}

// sort by the computed value
array.sort((a, b) => a[1] - b[1]);

// undecorate: remove the keys, leaving only the original elements
for (let i = 0; i < array.length; i++) {
    array[i] = array[i][0];
}

console.log(array);
```

The output is:

```none
getSortKey 4
getSortKey 16
getSortKey 8
getSortKey 2
getSortKey 6
[ '2', '4', '6', '8', '16' ]
```

Therefore, `getSortKey` was called just once for each element. If the array has repeated elements, then there would be repeated call to `getSortKey`, but that's still better than calling it all the time (and obviously this could be solved with memoization).

In the first `for` loop I replace each element by an array containing the element itself and the respective result of `getSortKey`. When sorting, I use those results as the sorting key, and in the second `for` loop I remove those results. In the end, the array is correctly sorted.

---

You can also use `map` to create another array, instead of using `for` loops:

```javascript
function getSortKey(item) {
    console.log('getSortKey', item);
    return parseInt(item);
}

let array = ['4', '16', '8', '2', '6'];
array = array
    // decorate: computes the key for each element and store it in the array
    .map(e => [ e, getSortKey(e) ])
    // sort by the computed value
    .sort((a, b) => a[1] - b[1])
    // undecorate: remove the keys, leaving only the original elements
    .map(e => e[0]);

console.log(array);
```

The problem is that each `map` call creates a new array, which makes this more memory consuming than the previous solution.


---
# Tests

I've created [a test in JSBench](https://jsbench.me/tokzh1it6r/1) and ran in Chrome, e did the same test in my machine using [Benchmark.js](https://benchmarkjs.com/).

In my machine, using memoization was way faster, and the Schwartzian solutions were the second best (usually, the solution without `map` was slightly better). In the browser, Schwartzian solutions were faster (not using `map` was also better), and memoization was second best. In both environments, a "pure" `sort` (no Schwartzian and no memoization) was always the slowest.

But as I said, that makes a significant difference only if the function is quite "expensive"/slow, and the array has lots of elements. For a small array, and/or a fast function, both Schwartzian transform and memoization were actually slower than a no-Schwartzian, no-memoized `sort`. Which means that - as everything you do in programming - you should analyze case by case if you really need to use those solutions.