AlexSkidanov's blog

By AlexSkidanov, 14 years ago, In Russian

Ферлонам, Хаустовым Павлам и сочувствующим -- можно ниже не читать :о)

 

Для остальных -- отличная задача.

Дан массив длины 2N. Первые N элементов и последние N элементов отсортированы по возрастанию. Надо отсортировать весь массив за линейное время с константой памяти.

 

Я предполагаю, что это не классика, потому что существует (неверное) (распространенное) мнение, что лучшая реализация Merge Sort требует O(N) памяти. Сам факт, что описанная выше задача имеет решение, очевидно, опровергает это.

 

UPD: Ваши решения можно проверить на случаях

6 7 8 9 10 1 2 3 4 5

и

1 3 5 7 9 2 4 6 8 10.

Почти любое наивное решение не способно решить один из них.

 

  • Vote: I like it
  • +65
  • Vote: I do not like it