Fast construction of wavelet trees

In this paper we describe a fast algorithm that creates a wavelet tree for a sequence of symbols. We show that a wavelet tree can be constructed in O(n⌈log⁡σ/log⁡n⌉) time where n is the number of symbols and σ is the alphabet size.