Advanced array sorting/re-arranging in Java

Question

So I have an array with the following theoretical values:

int[] elements = {A1, A2, B1, B2,
                  A3, A4, B3, B4,
                  C1, C2, D1, D2,
                  C3, C4, D3, D4};

Illustrative figure:

                  + - + - + - + - +
                  | A | A | B | B |
                  + - + - + - + - +
                  | A | A | B | B |
                  + - + - + - + - +
                  | C | C | D | D |
                  + - + - + - + - +
                  | C | C | D | D |
                  + - + - + - + - +

Simply put I would like the array to be re-arranged to the following form:

int[] elements = {A1, A2, A3, A4,
                  B1, B2, B3, B4,
                  C1, C2, C3, C4,
                  D1, D2, D3, D4};

Illustrative figure:

                  + - + - + - + - +
                  | A | A | A | A |
                  + - + - + - + - +
                  | B | B | B | B |
                  + - + - + - + - +
                  | C | C | C | C |
                  + - + - + - + - +
                  | D | D | D | D |
                  + - + - + - + - +

This particular example contains four sectors (A, B, C and D), but the algorithm I need should work however many or few sectors the array contains, and however many elements each sector contains.

The size of each sector is known (sector width and sector height) and also the amount of sectors (rows and columns). All sectors are of the exact same size (width and height). The amount of sectors has to be described as two values (rows ans columns) which is then multiplied to make up the actual sum of sectors. Eg. if 5 sectors are wanted, then 1 row and 5 columns could be specified.

Here follows an example of what a method preforming this sort could look like:

public int[] sectorSort(int[] elements,
                        int sectorWidth,
                        int sectorHeight,
                        int columns,
                        int rows);

Example of other sector setups:

                  Columns: 5
                  + - + - + - + - + - + - + - + - + - + - +
                  | A | A | B | B | C | C | D | D | E | E |
     Rows: 1      + - + - + - + - + - + - + - + - + - + - +
                  | A | A | B | B | C | C | D | D | E | E |
                  + - + - + - + - + - + - + - + - + - + - +

                  Columns: 2
                  + - + - + - + - +
                  | A | A | B | B |
                  + - + - + - + - +
                  | A | A | B | B |
                  + - + - + - + - +
                  | C | C | D | D |
     Rows: 3      + - + - + - + - +
                  | C | C | D | D |
                  + - + - + - + - +
                  | E | E | F | F |
                  + - + - + - + - +
                  | E | E | F | F |
                  + - + - + - + - +

I plan on using this to make an efficient sprite map class for a game engine I'm making. The elements in the array are ARGB color values, and the sectors are individual sprites. If the different sprites are arranged in the latter order then searching for individual sprites goes a lot faster and memory efficient.

Thank you!

EDIT1: Clarity.

EDIT2: Added more conditions and clarifications.

Answer 1

You're not going to get a better time complexity than this: It creates a new array and copies each sector into it.

static T[] sectorSort<T>(T[] elements, int sectorWidth, int sectorHeight, int columns, int rows)
        {
            T[] sortedElements = new T[elements.Length];
            int n = 0;
            int arrWidth = sectorWidth * columns;
            for(int secY = 0; secY < rows; secY++)
                for (int secX = 0; secX < columns; secX++)
                {
                    int baseIndex = secY * arrWidth * sectorHeight + secX * sectorWidth;
                    for(int y = 0; y < sectorHeight; y++)
                        for (int x = 0; x < sectorWidth; x++)
                        {
                            int sourceIndex = baseIndex + y * arrWidth + x;
                            sortedElements[n++] = elements[sourceIndex];
                        }
                }
            return sortedElements;
        }

I can still see a lot of optimizations that can be done, however reading your question I see this is done in loading time so don't fuss too much about it.

EDIT: Fixed code

EDIT2: Test setup (C#)

    int[] array = new int[]
    {
        11, 12, 13, 21, 22, 23, 51, 52, 53,
        14, 15, 16, 24, 25, 26, 54, 55, 56,
        17, 18, 19, 27, 28, 29, 57, 58, 59,
        31, 32, 33, 41, 42, 43, 61, 62, 63,
        34, 35, 36, 44, 45, 46, 64, 65, 66,
        37, 38, 39, 47, 48, 49, 67, 68, 69,
        71, 72, 73, 81, 82, 83, 91, 92, 93,
        74, 75, 76, 84, 85, 86, 94, 95, 96,
        77, 78, 79, 87, 88, 89, 97, 98, 99,
    };
    int[] sorted = sectorSort(array, 3, 3, 3, 3);
    for (int y = 0; y < 9; y++)
    {
        for (int x = 0; x < 9; x++)
            Console.Write(sorted[x + y * 9] + " | ");
        Console.WriteLine("\n");
    }

Answer 2

You could take a straight forward algorithm iterating all sectors and all elements therein to rearrange them. This would be O(n*m), n=number of sectors and m = number of elements per sector. But you would have to rearrange the whole array. As an alternative (if memory is critical) you could create a sector based view of the original array this would take O(n) for creating the view and then O(m) to read the values of a single sector.

So reading all sectors would require O(n*m) in both cases. What improvement do you expect?