But you have to quantify the max-min, cause it's quite easy for the data to make that way more expensive then "merge then sort". I.e., run your algo on [[0, 1000000000], [1, 2]]
Perhaps add a check to see if min-max is greater than K*N, and if so then use alternative method (e.g. merge sort)