Быстрая сортировка нечетных элементов - C#

Формулировка задачи:

Есть метод обычной быстрой сортировки, но нужно, чтобы сортировались только нечетные (по расположению) элементы, т.е элементы с четным индексом. По заданию нужно использовать только быструю сортировку. Несколько часов уже не могу ничего придумать.

                    Листинг программы
                
 
                            
                        
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace ConsoleApplication11
{
    class Program
    {
        static void QSort(int[] M, int LG, int PG)
        {
            int i = LG, j = PG, T;
            double X = M[((LG + PG) / 2)];
                while (i <= j)
                {
                    while (M[i] < X) i += 1;
                    while (M[j] > X) j -= 1;
                    if (i <= j)
                    {
                        T = M[i]; M[i] = M[j]; M[j] = T;
                        i += 1; j -= 1;
                    }
                }
                if (LG < j) QSort(M, LG, j);
                if (i < PG) QSort(M, i, PG);
        }
 
        static void Main(string[] args)
        {
            const int k = 9;
            int[] M = new int[k];
            Random rand = new Random();
            for (int i = 0; i < k; i++) { M[i] = rand.Next(-9, 9); }
            Console.WriteLine("Вывод исходного массива");
            for (int i = 0; i < M.Length; i++) { Console.Write(M[i] + " "); }
            Console.WriteLine();
 
            QSort(M, 0, M.Length - 1);
 
            Console.WriteLine("\n\nВывод отсортированного массива");
            for (int i = 0; i < M.Length; i++) { Console.Write(M[i] + " "); }
        }
    }
}

Решение задачи: «Быстрая сортировка нечетных элементов»

textual
                            Листинг программы 
                        
 
                        
                          
                    
using System;
using System.Linq;
using System.Collections.Generic;
 
class Program
{
    private static IEnumerable<int> QuickSort(IEnumerable<int> en)
    {
        int count = en.Count();
        if (count < 2) return en;
        int fst = en.First();
        if (count == 2) return fst > en.Last() ? en.Reverse() : en;
        ILookup<int, int> lookup = en.ToLookup(x => x.CompareTo(fst));
        return QuickSort(lookup[-1]).Concat(lookup[0]).Concat(QuickSort(lookup[1]));
    }
 
    public static void Main()
    {
        int[] arr = Enumerable.Repeat(new Random(), 20).Select(r => r.Next(100)).ToArray();
        Console.WriteLine(String.Join(", ", arr));
        Queue<int> que = new Queue<int>(QuickSort(arr.Where((_, i) => i % 2 == 0)));
        for (int i = 0; i < arr.Length; i += 2)
        {
            arr[i] = que.Dequeue();
        }
        Console.WriteLine(String.Join(", ", arr));
    }
}