Sort different runs of integers

Let S be a sequence of n elements divided into n/k subsequences each of length where all of the elements in any subsequence are larger than all of the elements of a preceding subsequence and smaller than all of the elements of a succeeding subsequence. Can you give an algorithm for sorting S? What is the optimal complexity?