using System;

using System.Collections.Generic;

using System.Linq;

​

public static class Program

{

    public static void Main()

    {

        var random = new Random();

        var source = Enumerable.Range(1, 15).Select(_ => random.Next(1, 6)).ToArray();

        Console.WriteLine($"Source: {String.Join(", ", source)}");

        SortTriplets(source, (a, b) =>

        {

            var ret = Comparer<int>.Default.Compare(a.Item1, b.Item1);

            if (ret == 0) ret = Comparer<int>.Default.Compare(a.Item2, b.Item2);

            return ret;

        });

        Console.WriteLine($"Sorted: {String.Join(", ", source)}");

    }

​

    public static void SortTriplets<T>(this T[] source, Comparison<(T, T, T)> comparison)

    {

        // Create an array of incremental indices (zero based)

        var indices = new int[source.Length / 3];

        for (int i = 0; i < indices.Length; i++) indices[i] = i;

​

        // Sort the indices according to the source array and the comparison delegate

        Array.Sort<int>(indices, (a, b) =>

        {

            a *= 3;

            b *= 3;

            return comparison(

                (source[a], source[a + 1], source[a + 2]),

                (source[b], source[b + 1], source[b + 2]));

        });

​

        // Rearrange the source array according to the sorted indices

        for (int i = 0; i < indices.Length - 1; i++)

        {

            int k = indices[i];

            while (k < i) k = indices[k];

            if (k == i) continue;

            Swap(i, k);

        }

​

        void Swap(int a, int b)

        {

            a *= 3;

            b *= 3;

            (T, T, T) temp = (source[a], source[a + 1], source[a + 2]);

            source[a] = source[b];

            source[a + 1] = source[b + 1];

            source[a + 2] = source[b + 2];

            source[b] = temp.Item1;

            source[b + 1] = temp.Item2;

            source[b + 2] = temp.Item3;

        }

    }

​

}

​