* Принципи на "разделяй и владей": разбиване на изходната задача на няколко подзадачи (разделяй), решаване на подзадачите и конструиране на решение на изходната задача (владей).

* Пример с двоично търсене.

* Намиране на максимален елемент (първия по големина) - n - 1 сравнения, n присвоявания в най-лошия случай, 1 присвояване в най-добрия случай, средния брой присвоявания е от порядък O(log n).

* Едновременно намиране на минимален и максимален елемент (първия и последния по големина) - 3n/2 сравнения ! Сравняваме 2 съседни елемента, по-големия го сравняване за max, а по-малкия - за min.

* Пълно сортиране - най-добрите алгоритми са O(n log n).

* Бързо сортиране с разделяне на дялове (Хоор, "разделяй и владей") - O(n²) в най-лошия случай, O(n) в най-добрия случай, O(n log n) средно. Сложността зависи от избора на елемент за разделяне на дялове.

* Когато търсим k-тия по големина елемент няма нужда да обработваме и двата дяла - отново O(n²) в най-лошия случай.

* Метод на Блум, Флойд, Прат, Ривест и Тарджан.
   - Нека имаме метод M за намиране на k-тия по големина елемент с 28n сравнения.
   - Медиана - елемент на масив, който се намира на позиция n/2 в сортирания масив.
   - Търсене на медиана на медианите:
        1. Разделяме масива на групи по 7 елемента.
        2. Сортираме всяка група и намираме медианата й (третия елемент) чрез сортиране по метода на мехурчето (или друг квадратичен метод).
        3. Намираме медианата на медианите по метод M (рекурсивно!).
    - Разделянато на дялове извършваме с така намерената медиана на медианите.
    - Оценка на метода (7(7-1)/2)(n/7) + 28(n/7) + 28(5n/7) = 3n +  4n + 20n = 27n (при всяко рекурсивно извикване областта намалява с поне 2n/7 елемента), т.е. предположението за 28n сравнения е вярно.

* Метод на Дур и Цвик [1995] - 2.95n сравнения, [2001] - (2+epsilon).n сравнения.

Допълнителна литература: [3] Лендерт Амерал, 3.12.