Split C array into n equal parts

Question

I am trying to split an array into n equal parts by calculating start and end indices. The address of the start and end elements will be passed into a function that will sort these arrays. For example, if arraySize = 1000, and n=2, the indices will be 0, 499, 999. So far I have the below code but for odd n, it is splitting it into more than n arrays. Another way I thought of doing this is by running through the loop n times, but I'm not sure where to start.

  int chunkSize = arraySize / numThreads;
  for (int start = 0; start < arraySize; start += chunkSize) {
      int end = start + chunkSize - 1;
      if (end > arraySize - 1) {
          end = arraySize - 1;
      }

      InsertionSort(&array[start], end - start + 1);
  }

EDIT: Here's something else I came up with. It seems to be working, but I need to do some more thorough testing. I've drawn this out multiple times and traced it by hand. Hopefully, there aren't any edge cases that will fail. I am already restricting n >= arraySize.

int chunkSize = arraySize / numThreads;
for (int i = 0; i < numThreads; i++) {
    int start = i * chunkSize;
    int end = start + chunkSize - 1;
    if (i == numThreads - 1) {
        end = arraySize - 1;
    }

    for (int i = start; i <= end; i++) {
        printf("%d ", array[i]);
    }
        printf("\n");
}

Answer 1

Calculate the minimum chunk size with the truncating division. Then calculate the remainder. Distribute this remainder by adding 1 to some chunks:

Pseudo-code:

chunk_size = array_size / N
bonus = array_size - chunk_size * N  // i.e. remainder

for (start = 0, end = chunk_size;
     start < array_size;
     start = end, end = start + chunk_size)
{
  if (bonus) {
    end++;
    bonus--;
  }

  /* do something with array slice over [start, end) interval */
}

For instance if array_size is 11 and N == 4, 11/N yields 2. The remainder ("bonus") is 3: 11 - 2*3. Thus the first three iterations of the loop will add 1 to the size: 3 3 3. The bonus then hits zero and the last chunk size will just be 2.

What we are doing here is nothing more than distributing an error term in a discrete quantization, in a way that is satisfactory somehow. This is exactly what happens when a line segment is drawn on a raster display with the Bresenham algorithm, or when an image is reduced to a smaller number of colors using Floyd-Steinberg dithering, et cetera.

Answer 2

You need to calculate your chunk size so that it is "rounded up", not down. You could do it using % operator and a more complex formula, but just using simple if is probably easier to understand:

int chunkSize = arraySize / numThreads;
if (chunkSize * numThreads < arraySize) {
    // In case arraySize is not exactly divisible by numThreads,
    // we now end up with one extra smaller chunk at the end.
    // Fix this by increseing chunkSize by one byte,
    // so we'll end up with numThread chunks and smaller last chunk.
    ++chunkSize;
}