1

I need to sort an array of positive integers. It's easy enough to do via JavaScript's sort method in O(N * log(N)):

let a = [4, 1, 3, 9, 7, 19, 11];
a.sort((a,b) => a - b);
return a;

// returns [1, 3, 4, 7, 9, 11, 19]

But, it seems like it can be done in O(N) using a JavaScript object? Looping through the array to add an integer into an object is O(N), then grabbing the values from that object is also O(N). (Alternatively, grab the keys and convert back to numbers).

let o = {};
let a = [4, 1, 3, 9, 7, 19, 11];

a.forEach(integer => { o[integer] = integer });

return Object.values(o);

// returns [1, 3, 4, 7, 9, 11, 19]

Drop the constant and we're looking at sorting positive integers in O(N) (sacrificing additional O(N) space). From everything I've read, this shouldn't be possible. What am I missing here?

shapirowned
  • 53
  • 4
  • 2
    Object.values() is clearly just doing a sort under the hood. Hiding the sort behind a stdlib call doesn't change the runtime complexity. – Chris Heald Feb 18 '20 at 05:44
  • 1
    Objects in JavaScript are unsorted, there is no guarantee as to the order you get. Most browsers seem to maintain the list of keys in sorted order - natural-sorted at that - but this is not a requirement and you should not rely on it. – Niet the Dark Absol Feb 18 '20 at 05:45
  • @NiettheDarkAbsol Implementations have had deterministic enumeration order for quite a while, and [ES2020](https://stackoverflow.com/a/58444013) will guarantee it. – CertainPerformance Feb 18 '20 at 05:52
  • @ChrisHeald Object.values() is just pulling the values into an array in linear time. It's not doing a sort. You can see the sort happening as you add positive integers into an object. – shapirowned Feb 18 '20 at 05:56
  • 1
    A sort of the keys is occurring *sometime*, though whether that's done when a property is added to the object or when the object is enumerated is up to the implementation – CertainPerformance Feb 18 '20 at 05:59
  • "*JavaScript's sort method in O(N * log(N)):*" there is no guarantee for this complexity. To my knowledge the spec doesn't require it, so it's up to the implementation. And for low number of elements some environments use a Bubble sort at `O(n^2)` – VLAZ Feb 18 '20 at 06:07

1 Answers1

3

The internal code used for setting and retrieving keys is implementation-dependent. The output (and order) is guaranteed (for all property enumeration methods, as of ES2020), but the mechanism is up to the implementer. You'd have to look at the engine source code for that.

I don't know the code that the different Javascript engines are running under the hood, but if you know of an upper bound on the number in the array, this is possible in O(n) (or, more precisely, O(n + k) where k is a constant - the upper bound) by using counting sort: create a map of the keys (similar to you're doing, but including the number of times each item appears), then iterate from 0 to the upper bound, checking to see if the number being iterated over is included in the keys. If so, push to the array:

let o = {};
let a = [4, 1, 3, 9, 7, 19, 11];

// O(n)
for (const num of a) {
  if (!o[num]) {
    o[num] = [];
  }
  o[num].push(num);
}

// O(n). This part isn't strictly necessary, but the alternative makes the code uglier
const max = Math.max(...a);
const result = [];
// O(k)
for (let i = 0; i <= max; i++) {
  if (o[i]) {
    // total of O(n) items pushed over the whole loop
    result.push(...o[i]);
  }
}

console.log(result);

If, like in your example, there are no repeated numbers, the code is significantly easier:

let o = {};
let a = [4, 1, 3, 9, 7, 19, 11];

for (const num of a) {
  o[num] = true;
}

// O(n)
const max = Math.max(...a);
const result = [];
// O(k)
for (let i = 0; i <= max; i++) {
  if (o[i]) {
    // total of O(n) items pushed over the whole loop
    result.push(i);
  }
}

console.log(result);
CertainPerformance
  • 356,069
  • 52
  • 309
  • 320