Mi sembra che tu ti stia complicando inutilmente la vita... perché confronti tutti gli elementi sotto con tutti quelli sopra (O(n^2))? Semplicemente cerca il massimo degli elementi prima di k (una passata O(k)), il minimo degli elementi oltre k (una passata (O(n-k)) e alla fine confronta: se il massimo pre-k è inferiore al minimo post-k allora il vettore è separato (il tutto in tempo lineare nella dimensione del vettore).

Per inciso, dovresti ormai aver imparato che il linguaggio va sempre indicato nel titolo della discussione...