The paper in this post doesn't use neural networks at all. It also includes the time to train the model in the sorting time, which the paper you linked doesn't. NN-sort trains on historic data to sort future data, which requires the distribution to be roughly the same, whearas this algorithm learns online.

This paper does not look like a strong paper, in particular it's very terse when describing the way the neural network is trained, which fails to convince that they did not train the neural network model on the sorted input. They are also not clear on their timings, it's not sure they include the training time in their benchmarks. For these reasons, it does not look very reproducible, and there's no obligation to cite non-reproducible work.

This one doesn’t use neural nets.

That paper has not been published. You can't claim a paper is prior, just because a draft was available earlier. Incidently it was send to the same conference as the OP paper. But it seems like it wasn't accepted, while the OP paper was.

this is not really the norm in computer science. it’s generally expected to cite things on arXiv although it is more of a grey area.

Well they did right by not citing it, as it was rejected for publication.

that’s not how things work. lots of well-regarded papers are initially rejected in peer review but are commonly discussed and cited while in the submission process at other venues.