def stooge_rec(data, i = 0, j = None):
	if j is None:
		j = len(data) - 1
	if data[j] < data[i]:
		data[i], data[j] = data[j], data[i]
	if j - i > 1:
		t = (j - i + 1) // 3
		stooge_rec(data, i, j - t)
		stooge_rec(data, i + t, j)
		stooge_rec(data, i, j - t)
	return data
				
def stooge(data):
	return stooge_rec(data, 0, len(data) - 1)

def slow_rec(data, i, j):
	if i >= j:
		return data
	m = (i + j) // 2
	slow_rec(data, i, m)
	slow_rec(data, m + 1, j)
	if data[m] > data[j]:
		data[m], data[j] = data[j], data[m]
	slow_rec(data, i, j - 1)
	return data
	
def slow(data):
	return slow_rec(data, 0, len(data) - 1)		
	
	
def stupid(data):
	i, size = 1, len(data)
	while i < size:
		if data[i - 1] > data[i]:
			data[i - 1], data[i] = data[i], data[i - 1]
			i = 1
		else:
			i += 1
	return data

def gnome(data):
	i, size = 1, len(data)
	while i < size:
		if data[i - 1] <= data[i]:
			i += 1
		else:
			data[i - 1], data[i] = data[i], data[i - 1]	
			if i > 1:
				i -= 1
	return data
	
def gnome_opt(data):
	i, j, size = 1, 2, len(data)
	while i < size:
		if data[i - 1] <= data[i]:
			i, j = j, j + 1
		else:
			data[i - 1], data[i] = data[i], data[i - 1]
			i -= 1
			if i == 0:
				i, j = j, j + 1
	return data

def bubble(data):
	changed = True
	while changed:
		changed = False
		for i in range(len(data) - 1):
			if data[i] > data[i+1]:
				data[i], data[i+1] = data[i+1], data[i]
				changed = True
	return data
	
def shaker(data):	
	up = range(len(data) - 1)		
	while True:
		for indices in (up, reversed(up)):
			swapped = False
			for i in indices:
				if data[i] > data[i+1]:  
					data[i], data[i+1] =  data[i+1], data[i]
					swapped = True
			if not swapped:
				return data
	
def odd_even(data):
	n = len(data)
	isSorted = 0
	while isSorted == 0:
		isSorted = 1
		for i in range(1, n - 1, 2):
			if data[i] > data[i + 1]:
				data[i], data[i + 1] = data[i + 1], data[i]
				isSorted = 0
				 
		for i in range(0, n - 1, 2):
			if data[i] > data[i + 1]:
				data[i], data[i + 1] = data[i + 1], data[i]
				isSorted = 0
	return data
	
def comb(data):
	gap = len(data)
	swaps = True
	while gap > 1 or swaps:
		gap = max(1, int(gap / 1.25))  # minimum gap is 1
		swaps = False
		for i in range(len(data) - gap):
			j = i + gap
			if data[i] > data[j]:
				data[i], data[j] = data[j], data[i]
				swaps = True
	return data

def quick(data):
	less = []
	pivotList = []
	more = []
	if len(data) <= 1:
		return data
	else:
		pivot = data[0]
		for i in data:
			if i < pivot:
				less.append(i)
			elif i > pivot:
				more.append(i)
			else:
				pivotList.append(i)
		less = quick(less)
		more = quick(more)
		return less + pivotList + more
			
def k(data):
	return k_rec(data, 0, len(data) - 1)
	
def k_rec(data, left, right):
	key = data[left]
	i = left
	j = right + 1
	k = left + 1
	p = left + 1
	temp = False
	while j - i >= 2:
		if key <= data[p]:
			if p != j and j != right + 1:
				data[j] = data[p]
			elif j == right + 1:
				temp = data[p]
			j -= 1
			p = j
		else:
			data[i] = data[p]
			i += 1
			k += 1
			p = k
	data[i] = key
	if temp:
		data[i + 1] = temp
	if left < i - 1:
		k_rec(data, left, i - 1)
	if right > i + 1:		
		k_rec(data, i + 1, right)
	return data

	//Придурковатая	
	function StoogeSort(&$arr, $i, $j) {
		if($arr[$j] < $arr[$i]) list($arr[$j], $arr[$i]) = array($arr[$i], $arr[$j]);
		if(($j - $i) > 1) {
			$t = ($j - $i + 1) / 3;
			StoogeSort($arr, $i, $j - $t);
			StoogeSort($arr, $i + $t, $j);
			StoogeSort($arr, $i, $j - $t);
		}
		return $arr;
	}
	
	//Вялая
	function SlowSort(&$arr, $i, $j) {
		if($i >= $j) return $arr;
		$m = ($i + $j) / 2;
		SlowSort($arr, $i, $m);
		SlowSort($arr, $m + 1, $j);
		if($arr[$m] > $arr[$j]) list($arr[$m], $arr[$j]) = array($arr[$j], $arr[$m]);
		SlowSort($arr, $i, $j - 1);
		return $arr;
	}
	
	//Туповатая
	function StupidSort($arr) {
		$i = 1; $size = count($arr);
		while($i < $size) {
			if($arr[$i - 1] <= $arr[$i]){
				++$i;
			} else {
				list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]);
				$i = 1;
			}
		}
		return $arr;
	}
	
	//Гном
	function GnomeSort($arr) {
		$i = 1; $size = count($arr);
		while($i < $size) {
			if($arr[$i - 1] <= $arr[$i]){
				++$i;
			} else {
				list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]);
				if($i > 1) --$i;
			}
		}
		return $arr;
	}
	
	//Гном (оптимизированный)
	function GnomeSort_opt($arr) {
		$i = 1; $j = 2; $size = count($arr);
		while($i < $size) {
			if($arr[$i - 1] <= $arr[$i]){
				$i = $j;
				++$j;
			} else {
				list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]);
				if(--$i == 0){
					$i = $j;
					$j++;
				}
			}
		}
		return $arr;
	}
	
	//Пузырьки
	function BubbleSort($arr) {
		$c = count($arr) - 1;
		do {
			$swapped = false;
			for ($i = 0; $i < $c; ++$i) {
				if ($arr[$i] > $arr[$i + 1]) {
					list($arr[$i + 1], $arr[$i]) = array($arr[$i], $arr[$i + 1]);
					$swapped = true;
				}
			}
		} while($swapped);
		return $arr;
	}
	
	//Шейкер
	function ShakerSort($arr){
		do{
			$swapped = false;
			for($i = 0; $i < count($arr); $i++){
				if(isset($arr[$i + 1])) {
					if($arr[$i] > $arr[$i+1]) {
						list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]);
						$swapped = true;
					}
				}			
			} 
			if ($swapped == false) break; 
			$swapped = false;
			for($i = count($arr) - 1; $i >= 0; $i--){
				if(isset($arr[$i - 1])){
					if($arr[$i] < $arr[$i - 1]) {
						list($arr[$i], $arr[$i - 1]) = array($arr[$i - 1], $arr[$i]);
						$swapped = true;
					}
				}
			}
		} while($swapped); 
		return $arr;
	}
	
	//Чёт-нечет
	function OddEvenSort($arr){
		$n = count($arr); 
		$sorted = false;
		while(!$sorted) {
			$sorted = true;
			for($i = 1; $i < $n - 2; $i += 2) {
				if($arr[$i] > $arr[$i + 1]) {
					list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]);
					$sorted = false;
				}				
			}
			for($i = 0; $i < $n - 1; $i += 2) {
				if($arr[$i] > $arr[$i + 1]) {
					list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]);
					$sorted = false;
				}				
			}			
		}		
	}
	
	//Расчёска
	function CombSort($arr){
		$gap = count($arr);
		$swap = true;
		while($gap > 1 || $swap){
			if($gap > 1) $gap /= 1.25;
			$swap = false;
			$i = 0;
			while($i + $gap < count($arr)){
				if($arr[$i] > $arr[$i + $gap]){
					list($arr[$i], $arr[$i + $gap]) = array($arr[$i + $gap], $arr[$i]);
					$swap = true;
				}
				++$i;
			}
		}
		return $arr;
	} 

	//Быстрая
	function QuickSort($arr) {
		$loe = $gt = array();
		if(count($arr) < 2) {
			return $arr;
		}
		$pivot_key = key($arr);
		$pivot = array_shift($arr);
		foreach($arr as $val){
			if($val <= $pivot){
				$loe[] = $val;
			}elseif ($val > $pivot){
				$gt[] = $val;
			}
		}
		return array_merge(QuickSort($loe), array($pivot_key => $pivot), QuickSort($gt));
	}
	
	//k-сортировка
	function K_Sort($arr) {
		K_Sort_rec($arr, 0, count($arr) - 1);
		return $arr;
	}
	
	function K_Sort_rec(&$arr, $left, $right) {
		$key = $arr[$left];
		$i = $left;
		$j = $right + 1;
		$k = $p = $left + 1;
		$temp = false;
		while($j - $i >= 2) {
			if($key <= $arr[$p]) {
				if(($p != $j) && ($j != ($right + 1))) {
					$arr[$j] = $arr[$p];
				} elseif($j == ($right + 1)) {
					$temp = $arr[$p];
				}
				--$j;
				$p = $j;
			} else {
				$arr[$i] = $arr[$p];
				++$i;
				++$k;
				$p = $k;
			}
		}
		$arr[$i] = $key;
		if($temp) $arr[$i + 1] = $temp;
		if($left < ($i - 1)) K_Sort_rec($arr, $left, $i - 1);
		if($right > ($i + 1)) K_Sort_rec($arr, $i + 1, $right);
	}