A sequence α(a1, , an) is k-sorted if for all 1i, jn, i jk implies aiaj. The number of k-sorted permutations of {1, , n} is denoted by Rk(n). We show that 1.4439n and 1.6933n are average case lower bounds on the numbers of comparisons needed to sort 3-sorted and 4-sorted sequences of length n, respectively. A compact form of a characteristic equation of degree k1 for a lower bound on Rk (n)/Rk(n1) is derived. From this characteristic equation, we also derive a good lower bound on the expected number of comparisons needed to sort k-sorted sequences for each k5.