This very recent paper shows a matching (conditional) lower bound of \Omega(n\log n): https://arxiv.org/abs/1902.10935 (the hardness is from a conjecture in network coding).
Very interesting. I was just wondering what the lower bound could be (beyond O(n) which seems fairly obvious, even though as a hobbyist I'd be hard pressed to even prove that).