Time complexity for partitioning a set and sorting the partition's subsets

Question

Suppose I have a function which partitions set S, |S|=n, into S/subsetSize subsets of size subsetSize and sorts each subset:

partitionAndSort(Set s, int subsetSize) {
   List partition = partitionList(s);
   for(Set subset: partition) {
      sort(subset);
   }
}

What's the running time of the function?

partition clearly takes O(n) because we go through the elements of the set one by one. subsetSize is considered to be a constant, hence an individual sort takes O(subsetSize*log(subsetSize))=O(1), and there are O(n/subsetSize)=O(n) sorting calls. Does the overall sorting take O(n)? Does that give a running time of O(n) for the function?

Answer 1

Yes, your function only needs O(n). Bear in mind, though, that it's not sorting the given set. Only the subsets. Hence there's no conflict with the n log n lower bound for (comparison-based) sorting of a set of n values, as you're not doing that.