[ksa]

как оптимизировать алгоритм до O (n), и не использовать. sort()

Как вариант...

const a = [9, 9, 9, 9, 8, 8, 4, 4, 4, 1, 2]
const o = a.reduce((o, v) => {
	o.list[v] = (o.list[v] ?? 0) + 1
	if (o.list[v] > o.max) o.max = o.list[v]
	return o
}, {list: {}, max: 0})
alert(o.max)