using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Runtime.InteropServices;
public static class Helper
{
public static void QuickSort(ref T[] array, int left, int right) where T : IComparable
{
int left_index = left;
int right_index = right;
T pivot = array[(left + right) / 2];
while (left_index <= right_index)
{
while (array[left_index].CompareTo(pivot) < 0)
left_index++;
while (array[right_index].CompareTo(pivot) > 0)
right_index--;
if (left_index <= right_index)
Swap(ref array[left_index++], ref array[right_index--]);
}
if (right_index > left)
QuickSort(ref array, left, right_index);
if (left_index < right)
QuickSort(ref array, left_index, right);
}
public static void Swap(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
}