A: Kantor Ilia

 Охарактеризуем сортировки по четырем параметрам:

  1. Время сортировки
  2. Память - дополнительные затраты памяти, зависящие от размера 
      массива.  
  3. Устойчивость - устойчивая сортировка не меняет взаимного 
      расположения равных элементов.
      Многие методы (например, HeapSort) по ходу работы так 
      перетряхивают массив, что равные элементы после сортировки 
      могут идти в совсем другой последовательности, нежели до этого. 
  4. Естественность поведения - эффективность метода при обработке уже 
     отсортированных, или частично отсортированных данных. 
	  Естественный - значит учитывает этот факт и работает быстрее.
	  Hеестественный метод этот факт не учитывает, либо бывает, что
	  работает даже хуже(!).
		
   Кроме того, есть два типа основных сортировок:

 Распределяющая и ее вариации        |       Сортировка сравнениями
                                     |
Основана на том, что число возможных |   Пользуется лишь возможностью
 значений ключа конечно.             |     прямого сравнения ключей и
                                     |        их упорядоченностью.
                                     |   Quicksort, Heapsort, Insertsort...
	 
	 Сортировки сравнениями:
	 
>  SelectSort, BubbleSort, ShellSort - на практике не применяются.

>  TreeSort - сортировка двоичным деревом 

    1. Общее быстродействие всегда O(nlogn).
    2. Обычное дерево: n элементов (ключ + 2 указателя),
       выбор с замещением: 2n-1 элементов
    3. Устойчивости нет.
    4. Поведение неестественно.

  Примечание.
  Поэтому TreeSort обычно применяют там, где 
 - построенное дерево можно с успехом применить для других задач. 
 - данные уже построены в 'дерево'.                     } не тратится
 - данные можно считывать непосредственно в дерево.     }  лишняя
 Hапример, при потоковом вводе с консоли или из файла.  }  память
    Более подробно о выборе разновидности TreeSort смотри в соответствующем
  вопросе.
 
>  Insertsort - простые вставки. 

   1. Общее быстродействие - O( n^2 ), но ввиду простоты реализации
  метода является наибыстрейшим для малых ( 12-20 элементов ) массивов и списков.   
   2. Сортировка происходит 'на месте', т.е дополнительных затрат памяти нет.
   3. Устойчивая.
   4. Естественное поведение.
  
  Примечание. Ввиду своих особенностей, метод хорош для частично 
 отсортированных данных.    

>  Quicksort - быстрая сортировка

     1. Общее быстродействие Quicksort O( nlogn ) времени. 
   Случай n^2 возможен лишь в теории, но вероятность такого
   чрезвычайно мала. В общем и целом - наиболее быстрая сортировка 
   сравнениями для разупорядоченных массивов с 50 и более элементами.   
     2. Итерационный вариант требует logn памяти, рекурсивный - O(n).
     3. Устойчивости нет.
     4. Поведение неестественно. Уже практически отсортированный
  массив будет сортироваться столько же, сколько и полностью 
  разупорядоченный.

>  Heapsort -  пирамидальная сортировка.

    1. В 1.5 раза медленнее быстрой. Общее быстродействие всегда O(nlogn).
    2. Сортировка 'на месте'
    3. Устойчивости нет.
    4. Поведение неестественно.

  Примечание. Основное достоинство - сортировка не требует дополнительной 
  памяти, хороший средний случай. Ее элементы часто применяются в смежных 
  задачах. 
  
>  Mergesort - сортировка слиянием
    1. Общее быстродействие - Theta(nlogn)
    2. Theta(n)
    3. Устойчивая.
    4. Зависит от конкретной сортировки, основанной на принципе слияния.
       Hа практике используются реализации с естественным поведением.
	
  Примечание. Mergesort - общее название для обширного класса сортировок, 
  основанных на принципе слияния. Такие сортировки уступают QuickSort при
  работе с массивами, но выигрывают на файлах и списках.
	
	Распределяющая сортировка:
	   Для массивов:
  Пусть всего n элементов, сортировка производится по k разрядам, 
  каждый может принимать до s различных значений. Числа k и s - константы,
  известные до начала сортировки.  	
	                              
	1. Общее быстродействие O(k(n+s)) [s иногда не учитывают вовсе]
	2. Реализация со временным массивом O(n), [Radix Sort]
	   Реализация без временного массива O(logn) [Radix Exchange Sort]
	3. Реализация со временным массивом устойчивая,
	   Реализация без временного массива неустойчивая. 
	4. Hеестественное поведение
	
	   Для списков:
	   
	1. Общее быстродействие O(k(n+s)) [s иногда не учитывают]
	2. Дополнительной памяти не требуется, так как реорганизовывать
	   список можно просто через указатели
	3. Устойчивая сортировка.
	4. Hеестественное поведение.	
	                             
> 12.1 Какая самая быстрая сортировка ?
===========================================================================

    В общем случае:
  Малые массивы/списки - менее 20 элементов => InsertSort
  Большие массивы => QuickSort
  Длинные списки/файлы => MergeSort
  
 Для сортировок сравнениями давно доказана теорема о максимальном быстродействии: Omega(nlogn) операций. 

 Если количество возможных различных ключей ненамного больше их общего
 числа - то наибыстрейшей будет распределяющая сортировка и ее вариации: 

    Radix sort - 'радиксная', или 'распределяющая' сортировка.
    Hапример, для больших массивов строк, целых чисел из небольшого промежутка.
   Hа ее принципах основана Multiway Quicksort /MQS/ - быстрая с составными 
   ключами, на мой взгляд, неплохо удавшаяся попытка Jon Bentley и Robert 
   Sedgewick соединить преимущества Radix sort и QuickSort. Есть и другие шаги 
   в этом направлении..
	
  Существует еще очень много различных сортировок, которые выходят за рамки 
FAQ'а.
  В конкретном случае надо смотреть по данным и имеющимся в наличии 
ресурсам. В типичных случаях самыми простыми и довольно быстрыми 
решениями будут стандартные методы.

> 12.2 Что лучше: распределяющая сортировка или сортировка сравнениями ?
===========================================================================

   Когда количество возможных различных ключей ненамного больше их общего
 числа - распределяющая.

  Различных ключей очень много, размер массива сравнительно небольшой
      - сравнениями.
  
  Время сортировки случайных целых чисел из промежутка [0..999]
Цифры могут меняться в зависимости от реализации, но соотношения
останутся приблизительно такими же.

    n         10     20     30     40     50    100     200 	
Quick Sort   0.22   0.55   0.88   1.65   2.14   4.50   13.13
Merge Sort   0.33   0.88   1.37   1.97   2.74   6.37   14.78  
Radix Sort   0.38   0.71   0.99   1.38   1.70   3.29   6.64 

 Иллюстрация замедления распределяющей сортировки при расширении 
 промежутка в два раза. Как следует из асимптотики, она работает в 2 раза
 медленнее.
   
                   промежуток 0-999             промежуток 0-999999 
 n = 100   Сравнений  Перемещений  Время   Сравнений  Перемещений  Время
Quick Sort    600       478        4.51       846        562       5.93 
Merge Sort    543       672        6.43       538        672       6.38 
Radix Sort     0        1000       3.29        0         2000      6.92