using System;
using System.Collections.Generic;
 
public class Test
{
	static List<int> RandomList(int size) {
		List<int> ret = new List<int>(size);
		Random rand = new Random(1);
		for (int i = 0; i < size; i++) {
			ret.Add(rand.Next(size));
		}
		return ret;
	}
 
	static int MyPartition(List<int> list, int left, int right)
    {
    	int start = left;
        int pivot = list[start];
        left++;
        right--;
 
        while(true)
        {
            while(left <= right && list[left] <= pivot)
                left++;
 
            while(left <= right && list[right] > pivot)
                right--;
 
            if(left > right)
            {
                list[start] = list[left - 1];
                list[left - 1] = pivot;
 
            	return left;
            }
 
 
            int temp = list[left];
            list[left] = list[right];
            list[right] = temp;
 
        }
    }
 
    static void MyQuickSort(List<int> list, int left, int right)
    {
        if(list == null || list.Count <= 1)
            return;
 
        if(left < right)
        {
            int pivotIdx = MyPartition(list, left, right);
        	//Console.WriteLine("MQS " + left + " " + right);
        	//DumpList(list);
            MyQuickSort(list, left, pivotIdx - 1);
            MyQuickSort(list, pivotIdx, right);
        }
    }
 
    static void DumpList(List<int> list) {
    	list.ForEach(delegate(int val)
        {
            Console.Write(val);
            Console.Write(", ");
        });
        Console.WriteLine();
    }
 
	public static void Main()
	{
        List<int> list = RandomList(100);
        DumpList(list);
        MyQuickSort(list, 0, list.Count);
        DumpList(list);
    }
}

dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKCnB1YmxpYyBjbGFzcyBUZXN0CnsKCXN0YXRpYyBMaXN0PGludD4gUmFuZG9tTGlzdChpbnQgc2l6ZSkgewoJCUxpc3Q8aW50PiByZXQgPSBuZXcgTGlzdDxpbnQ+KHNpemUpOwoJCVJhbmRvbSByYW5kID0gbmV3IFJhbmRvbSgxKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IHNpemU7IGkrKykgewoJCQlyZXQuQWRkKHJhbmQuTmV4dChzaXplKSk7CgkJfQoJCXJldHVybiByZXQ7Cgl9CgkKCXN0YXRpYyBpbnQgTXlQYXJ0aXRpb24oTGlzdDxpbnQ+IGxpc3QsIGludCBsZWZ0LCBpbnQgcmlnaHQpCiAgICB7CiAgICAJaW50IHN0YXJ0ID0gbGVmdDsKICAgICAgICBpbnQgcGl2b3QgPSBsaXN0W3N0YXJ0XTsKICAgICAgICBsZWZ0Kys7CiAgICAgICAgcmlnaHQtLTsKCiAgICAgICAgd2hpbGUodHJ1ZSkKICAgICAgICB7CiAgICAgICAgICAgIHdoaWxlKGxlZnQgPD0gcmlnaHQgJiYgbGlzdFtsZWZ0XSA8PSBwaXZvdCkKICAgICAgICAgICAgICAgIGxlZnQrKzsKCiAgICAgICAgICAgIHdoaWxlKGxlZnQgPD0gcmlnaHQgJiYgbGlzdFtyaWdodF0gPiBwaXZvdCkKICAgICAgICAgICAgICAgIHJpZ2h0LS07CgogICAgICAgICAgICBpZihsZWZ0ID4gcmlnaHQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGxpc3Rbc3RhcnRdID0gbGlzdFtsZWZ0IC0gMV07CiAgICAgICAgICAgICAgICBsaXN0W2xlZnQgLSAxXSA9IHBpdm90OwoKICAgICAgICAgICAgCXJldHVybiBsZWZ0OwogICAgICAgICAgICB9CiAgICAgICAgICAgIAoKICAgICAgICAgICAgaW50IHRlbXAgPSBsaXN0W2xlZnRdOwogICAgICAgICAgICBsaXN0W2xlZnRdID0gbGlzdFtyaWdodF07CiAgICAgICAgICAgIGxpc3RbcmlnaHRdID0gdGVtcDsKCiAgICAgICAgfQogICAgfQoKICAgIHN0YXRpYyB2b2lkIE15UXVpY2tTb3J0KExpc3Q8aW50PiBsaXN0LCBpbnQgbGVmdCwgaW50IHJpZ2h0KQogICAgewogICAgICAgIGlmKGxpc3QgPT0gbnVsbCB8fCBsaXN0LkNvdW50IDw9IDEpCiAgICAgICAgICAgIHJldHVybjsKCiAgICAgICAgaWYobGVmdCA8IHJpZ2h0KQogICAgICAgIHsKICAgICAgICAgICAgaW50IHBpdm90SWR4ID0gTXlQYXJ0aXRpb24obGlzdCwgbGVmdCwgcmlnaHQpOwogICAgICAgIAkvL0NvbnNvbGUuV3JpdGVMaW5lKCJNUVMgIiArIGxlZnQgKyAiICIgKyByaWdodCk7CiAgICAgICAgCS8vRHVtcExpc3QobGlzdCk7CiAgICAgICAgICAgIE15UXVpY2tTb3J0KGxpc3QsIGxlZnQsIHBpdm90SWR4IC0gMSk7CiAgICAgICAgICAgIE15UXVpY2tTb3J0KGxpc3QsIHBpdm90SWR4LCByaWdodCk7CiAgICAgICAgfQogICAgfQogICAgCiAgICBzdGF0aWMgdm9pZCBEdW1wTGlzdChMaXN0PGludD4gbGlzdCkgewogICAgCWxpc3QuRm9yRWFjaChkZWxlZ2F0ZShpbnQgdmFsKQogICAgICAgIHsKICAgICAgICAgICAgQ29uc29sZS5Xcml0ZSh2YWwpOwogICAgICAgICAgICBDb25zb2xlLldyaXRlKCIsICIpOwogICAgICAgIH0pOwogICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKCk7CiAgICB9CiAgICAKCXB1YmxpYyBzdGF0aWMgdm9pZCBNYWluKCkKCXsKICAgICAgICBMaXN0PGludD4gbGlzdCA9IFJhbmRvbUxpc3QoMTAwKTsKICAgICAgICBEdW1wTGlzdChsaXN0KTsKICAgICAgICBNeVF1aWNrU29ydChsaXN0LCAwLCBsaXN0LkNvdW50KTsKICAgICAgICBEdW1wTGlzdChsaXN0KTsKICAgIH0KfQ==