Martin Robert's directed me to this StackExchange discussion, which states that the median is approximately (asymptotically) n! / n^m * S2(m,n), where S2(m,n) is the Stirling number of the second kind.