Give variables meaningful names

While short variable names sometimes make sense, it's really hard to make sense of your code when it's mostly one and two letter variables. If you do stick with very short variable names for some reason, make sure you explain them in comments, and/or if you want to use the same names as in some paper or online article, use exactly the same names and add a reference to that paper or article.

Use the standard library

There is lots of functionality in the standard library that you should use instead of reinventing the wheel. For example:

• Instead of implementing your own swap(), just use std::swap().
• Use std::sort() instead of insertionSort().
• Use std::partition() instead of writing your own.
• Use std::midpoint() if you can use C++20.

This should not be a class

In C++ it is perfectly fine to have functions that live outside of a class. A class without any member variables is not very useful. So write a free function KWayPartition(). Any helper functions can be put into an anonymous namespace so they don't pollute the global namespace.

I also don't see why you have a virtual function Partition(), which in turn just calls the non-virtual KPartition(). Making a class virtual has a performance impact, so doing it for no good reason is bad.

Use std::size_t for indices

Using int for indices is problematic on 64-bit platforms where an array can have more elements than you can represent using an int. Use std::size_t for sizes, counts and indices where possible, as that type is guaranteed to be large enough for anything that can be stored in memory.

Consider passing iterators

Instead of passing a pointer to an array and one or more indices, consider passing iterators instead. As a bonus, this would allow your \$k\$-way partitioning algorithm to work on some containers other than regular arrays. Since you already made your code a template, it shouldn't be very hard; just make T the iterator type. Although you might also want to consider the possibility of the set of elements you want to partition and the set of pivots to be stored in different container types; in that case you want to have multiple template parameters.

Even better would be to pass ranges, if you can use C++20.

Example rewrite

Here is how it can look instead with iterators and use of the standard library. It also outputs the "borders".

template<typename ArrayIt, typename PivotsIt, typename BordersIt>
void KWayPartition(ArrayIt array_begin, ArrayIt array_end,
                   PivotsIt pivots_begin, PivotsIt pivots_end,
                   BordersIt borders_begin, BordersIt borders_end)
{
    if (array_begin == array_end) {
        return;
    }

    if (pivots_begin == pivots_end) {
        std::sort(array_begin, array_end);
    } else {
        auto pivots_mid = pivots_begin;
        std::advance(pivots_mid, std::distance(pivots_begin, pivots_end) / 2);
        auto array_mid = std::partition(array_begin, array_end, [&](auto& item){
            return item < *pivots_mid;
        });

        auto borders_mid = borders_begin;
        std::advance(borders_mid, std::distance(borders_begin, borders_end) / 2);
        *borders_mid = array_mid;

        KWayPartition(array_begin, array_mid, pivots_begin, pivots_mid, borders_begin, borders_mid);
        KWayPartition(++array_mid, array_end, ++pivots_mid, pivots_end, ++borders_mid, borders_end);
    }
}

The way to use it is like so:

std::vector<int> data = …;
std::vector<int> pivots = …;
std::vector<decltype(data)::iterator> borders(pivots.size());
KWayPartition(data.begin(), data.end(), pivots.begin(), pivots.end(), borders.begin(), borders.end());

And the vector borders will contain iterators into data where the borders of the partitions are, in the same way std::partition() returns a single iterator. Changing this into an array of pairs of iterators describing the start and end of each partition is left as an excercise for the reader. The above code also doesn't handle all corner cases properly, for example borders might not be filled in correctly if some of the partitions are empty.