Sort Order Only

[ghost]

I wanted to use this project but found it was difficult to use it with SoA formatted data.

For example.

struct CodePacket final {
  // 'a' is used for comparison
  int a[64];
  // 'b' is a value associated with 'a'
  int b[64];
};

In order to sort this structure with this library, I'd have to create comparator that handles indices to the structure data instead of directly accessing them. For example:

struct LessThan final {

  const CodePacket& cp;

  LessThan(const CodePacket& cp_) : cp(cp_) {}

  bool operator () (int i, int j) const noexcept {
    return cp.a[i] < cp.b[i];
  }
};

Then then pass an array of indices to the sort network:

int indices[64] = { 0, 1, 2, 3, 4, ... };

StaticTimSort<64> sort;

sort(indices, LessThan(cp));

/* Sort based on new values in 'indices' */

When the amount elements are either a bit large (larger than 8 or 16) or they're template parameters, this gets pretty tedious.

Do you think it would be useful to allow indices to be returned, so that the data can be moved after the sort? I wonder if it would be more efficient that way.

struct CodePacket final {
  int a[64];
  int b[64];

  constexpr CodePacket sorted(const int* order) const noexcept {
    CodePacket out;
    for (int i = 0; i < 64; i++) {
      out.a[i] = a[order[i]];
      out.b[i] = b[order[i]];
    }
    return out;
  }
};

void someFunction() {

  CodePacket cp;

  /* .... */

  int order[64];

  StaticTimeSort<64> sort;

  sort(cp.a, std::less<int>(), order);

  CodePacket sorted_cp = cp.sorted(order);
}

But ultimately it's not about efficiency too much, it's more about eliminating the need to initialize the array of indices before calling the sort function and having to write custom comparators for POD data. What are your thoughts on this?

[Vectorized]

You'll just have to initialize the array of indices and write the comparator. It will be negligible compared to the sorting time.

Just wrap up the whole sorting part in a function if you want to make the code neater.

This is what you may want to do.

#include "static_sort.h"

#include <iostream>
#include <vector>

struct CodePacket final {
    // 'a' is used for comparison
    int a[64];
    // 'b' is a value associated with 'a'
    int b[64];

    CodePacket sorted() const noexcept {

        struct C {
            const int *p;
            bool operator < (C c) const { return *p < *c.p; }
        };

        C c[64];

        for (int i = 0; i < 64; ++i) {
            c[i].p = a + i;
        }

        CodePacket out;

        StaticSort<64> staticSort;
        staticSort(c);

        for (int i = 0; i < 64; i++) {
            out.a[i] = a[c[i].p - a];
            out.b[i] = b[c[i].p - a];
        }

        return out;
    }
};

int main(int argc, const char * argv[])
{
    CodePacket cp, cpSorted;

    for (int i = 0; i < 64; ++i) {
        cp.a[i] = rand() % 100;
        cp.b[i] = rand() % 100;
    }
    cpSorted = cp.sorted();

    for (int i = 0; i < 64; ++i) {
        std::cout << cpSorted.a[i] << ", " << cpSorted.b[i] << "\n";
    }

    return 0;
}

[ghost]

I decided to rearrange my data, since it wasn't benefiting from SoA as much as I'd hoped. I probably will be using this library after all if the tests show any benefit. Thanks for the response! Neat library