Алгоритм сортировки

Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Формулировка задачи

Дан массив A из n элементов:

<math>a_1, a_2,\dots, a_n</math>,

Будем считать, что с каждым элементом <math>a_i</math> (помимо другой информации, не влияющей на сортировку) связан ключ <math>k_i\in K</math>. На множестве ключей <math>K</math> задано отношение порядка — линейного (или совершенного) упорядочивания, для которого были бы выполнены следующие условия:

1. закон трихотомии: для любых <math>x, y\in K</math> либо <math>x < y</math>, либо <math>x > y</math>, либо <math>x = y</math>;
2. транзитивность: для любых <math>x, y, z\in K</math> если <math>x < y</math> и <math>y < z</math>, то <math>x < z</math>.

Задачей сортировки по неубыванию является нахождение перестановки элементов <math>p(1), p(2),\dots, p(n)</math> с индексами от <math>1, 2,\dots, n</math>, при которой ключи располагаются в порядке неубывания:

<math>k_{p(1)} \leqslant k_{p(2)} \leqslant \dots \leqslant k_{p(n)}</math>

В результате работы алгоритма и применения перестановки получается отсортированный массив:

<math>a_{p(1)}, a_{p(2)},\dots, a_{p(n)}</math>

Аналогично можно определить сортировку по невозрастанию.

Оценка алгоритма сортировки

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

• Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O(n log log n log log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O(log² n) операций. При этом число n должно быть заранее известно;
• Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O(log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O(1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Оптимальность <math>O(n \log(n))</math>

Задача сортировки в общем случае предполагает, что единственной обязательно наличествующей операцией для элементов является сравнение. Это делает невозможным реализацию алгоритма Хана, использующего арифметические действия. Рассмотрим схему алгоритма, когда единственным возможным действием над элементами является их сравнение.

Пусть по ходу работы алгоритмом производится <math>k</math> сравнений. Ответом на сравнение двух элементов <math>a</math> и <math>b</math> может быть один из двух вариантов (<math>a<b</math> или <math>a>b</math>). Значит, всего возможно <math>2^k</math> вариантов комбинаций ответов на <math>k</math> вопросов.

Количество перестановок из <math>n</math> элементов равно <math>n!</math>. Для того, чтобы можно было провести сюръекцию из множества ответов на сравнения на множество перестановок, количество сравнений должно быть не меньше, чем <math>\log_2{n!}</math> (это обеспечивается тем, что сравнение — единственная разрешённая операция).

Прологарифмировав формулу Стирлинга, можно обнаружить, что <math>\log_2{n!}=\log_2{\left( \sqrt{2 \pi n}\left( \frac{n}{e} \right) ^ n \right)}=\log_2{\sqrt{2 \pi n}}+n\log_2{n}-n\log_2{e} \sim n\log_2{n}=O(n\log{n})</math>

Свойства и классификация

• Устойчивость (англ. stability) — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами.
• Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

• Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет <math>O</math>(<math>n \cdot \log n</math>), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

• Внутренняя сортировка оперирует массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте без дополнительных затрат.
  • В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
• Внешняя сортировка оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), то есть в данный момент «виден» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью.
  • Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
  • Объём данных не позволяет им разместиться в ОЗУ.

Также алгоритмы классифицируются по:

• потребности в дополнительной памяти или её отсутствию
• потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой

Список алгоритмов сортировки

В этой таблице <math>n</math> — это количество записей, которые необходимо упорядочить, а <math>k</math> — это количество уникальных ключей.

Алгоритмы устойчивой сортировки

• Сортировка пузырьком (англ. Bubble sort) — для каждой пары индексов производится обмен, если элементы расположены не по порядку. Сложность алгоритма: <math>O(n^2)</math>.
• Сортировка перемешиванием (англ. Cocktail sort). Сложность алгоритма: <math>O(n^2)</math>.
• Гномья сортировка (англ. Gnome sort). — схожа с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — <math>O(n^2)</math>.
• Сортировка вставками (Insertion sort) — Определяем, где текущий элемент должен находиться в упорядоченном списке, и вставляем его туда. Сложность алгоритма: <math>O(n^2)</math>.
• Сортировка слиянием (Merge sort) — выстраиваем первую и вторую половину списка отдельно, а затем объединяем упорядоченные списки. Сложность алгоритма: <math>O(n \log n)</math>. Требуется <math>O(n)</math> дополнительной памяти.
• Сортировка с помощью двоичного дерева (англ. Tree sort). Сложность алгоритма: <math>O(n \log n)</math>. Требуется <math>O(n)</math> дополнительной памяти.
• Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием). Сложность алгоритма: <math>O(n \log n)</math>. Требуется <math>O(n)</math> дополнительной памяти. Разработан для использования в языке Python.
• Сортировка подсчётом (Counting sort). Сложность алгоритма: <math>O(n+k)</math>. Требуется <math>O(n+k)</math> дополнительной памяти.
• Блочная сортировка (Корзинная сортировка, Bucket sort) — требуется <math>O(k)</math> дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций «переставить» и «сравнить». Сложность алгоритма: <math>O(n)</math>.
• Поразрядная сортировка (она же цифровая сортировка) — сложность алгоритма: <math>O(nk)</math>; требуется <math>O(k)</math> дополнительной памяти.

Алгоритмы неустойчивой сортировки

• Сортировка выбором (англ. Selection sort) — поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка. Сложность алгоритма: <math>O(n^2)</math>.
• Сортировка Шелла (Shell sort). сложность алгоритма: <math>O(n \log_2{n})</math>; улучшение сортировки вставками.
• Сортировка расчёской (Comb sort) — сложность алгоритма: <math>O(n \log{n})</math>
• Пирамидальная сортировка (сортировка кучи, Heapsort) — сложность алгоритма: <math>O(n \log{n})</math>; превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
• Плавная сортировка (Smoothsort) — сложность алгоритма: <math>O(n \log{n})</math>
• Быстрая сортировка (Quicksort), в варианте с минимальными затратами памяти — сложность алгоритма: <math>O(n \log{n})</math> — среднее время, <math>O(n^2)</math> — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине. При использовании <math>O(n)</math> дополнительной памяти, можно сделать сортировку устойчивой.
• Интроспективная сортировка (Introsort) — сложность алгоритма: <math>O(n \log{n})</math>, сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает <math>\log{n}</math>.
• Терпеливая сортировка (Patience sorting) — сложность алгоритма: <math>O(n \log{n})</math> — наихудший случай, требует дополнительно <math>O(n)</math> памяти, также находит самую длинную увеличивающуюся подпоследовательность
• Stooge sort — рекурсивный алгоритм сортировки с временной сложностью <math>O(n^{\log_{1{,}5}{3}}) \approx O(n^{2.71})</math>.

Непрактичные алгоритмы сортировки

• Bogosort — <math>O(n \cdot n!)</math> в среднем. Произвольно перемешать массив, проверить порядок.
• Сортировка перестановкой — <math>O(n \cdot n!)</math> — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.
• Глупая сортировка (Stupid sort) — <math>O(n^3)</math>; рекурсивная версия требует дополнительно <math>O(n^2)</math> памяти
• Bead Sort — <math>O(n)</math> или <math>O( \sqrt n)</math>, требуется специализированное аппаратное обеспечение
• Блинная сортировка (Pancake sorting) — <math>O(n)</math>, требуется специализированное аппаратное обеспечение

Алгоритмы, не основанные на сравнениях

• Блочная сортировка (Корзинная сортировка, Bucket sort)
• Лексикографическая или поразрядная сортировка (Radix sort)
• Сортировка подсчётом (Counting sort)

Прочие алгоритмы сортировки

• Топологическая сортировка
• Внешняя сортировка

Сортировка строк

Одним из наиболее частых приложений алгоритмов сортировки является сортировка строк. Обычно она производится так: сначала множество строк сортируется по первому символу каждой строки, затем каждое подмножество строк, имеющих одинаковый первый символ, сортируется по второму символу, и так до тех пор, пока все строки не будут упорядочены. При этом отсутствующий символ (при сравнении строки длины N со строкой длины N+1) считается меньше любого символа.

Применение данного метода к строкам, представляющим собой числа в естественной записи, выдаёт контринтуитивные результаты: например, «9» оказывается больше, чем «11», так как первый символ первой строки имеет бо́льшее значение, чем первый символ второй. Для исправления этой проблемы алгоритм сортировки может преобразовывать сортируемые строки в числа и сортировать их как числа. Такой алгоритм называется «числовой сортировкой», а описанный ранее — «строковой сортировкой».

См. также

• O-большое
• Временная сложность алгоритма
• Ёмкостная сложность алгоритма
• Внешняя сортировка
• Сортирующие сети (сравнение)
• Сравнивание
• Трансформация Шварца
• Параллельная сортировка
• Индексная сортировка

Литература

• Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 5-8459-0082-4.
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4.
• Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4.
• Magnus Lie Hetland. Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с. — ISBN 978-1-4302-3237-7.

Ссылки

• [informatics.mccme.ru/moodle/course/view.php?id=3 Теория, задачи, тестирующая система]
• [algolist.manual.ru/sort/index.php Алгоритмы сортировки на algolist.manual.ru]
• [www.sorting-algorithms.com Анимированное сравнение алгоритмов сортировки]  (англ.)
• [airtucha.github.io/SortVis/ Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом]

Отрывок, характеризующий Алгоритм сортировки

– Но как его рана? Вообще в каком он положении?
– Вы, вы… увидите, – только могла сказать Наташа.
Они посидели несколько времени внизу подле его комнаты, с тем чтобы перестать плакать и войти к нему с спокойными лицами.
– Как шла вся болезнь? Давно ли ему стало хуже? Когда это случилось? – спрашивала княжна Марья.
Наташа рассказывала, что первое время была опасность от горячечного состояния и от страданий, но в Троице это прошло, и доктор боялся одного – антонова огня. Но и эта опасность миновалась. Когда приехали в Ярославль, рана стала гноиться (Наташа знала все, что касалось нагноения и т. п.), и доктор говорил, что нагноение может пойти правильно. Сделалась лихорадка. Доктор говорил, что лихорадка эта не так опасна.
– Но два дня тому назад, – начала Наташа, – вдруг это сделалось… – Она удержала рыданья. – Я не знаю отчего, но вы увидите, какой он стал.
– Ослабел? похудел?.. – спрашивала княжна.
– Нет, не то, но хуже. Вы увидите. Ах, Мари, Мари, он слишком хорош, он не может, не может жить… потому что…


Когда Наташа привычным движением отворила его дверь, пропуская вперед себя княжну, княжна Марья чувствовала уже в горле своем готовые рыданья. Сколько она ни готовилась, ни старалась успокоиться, она знала, что не в силах будет без слез увидать его.
Княжна Марья понимала то, что разумела Наташа словами: сним случилось это два дня тому назад. Она понимала, что это означало то, что он вдруг смягчился, и что смягчение, умиление эти были признаками смерти. Она, подходя к двери, уже видела в воображении своем то лицо Андрюши, которое она знала с детства, нежное, кроткое, умиленное, которое так редко бывало у него и потому так сильно всегда на нее действовало. Она знала, что он скажет ей тихие, нежные слова, как те, которые сказал ей отец перед смертью, и что она не вынесет этого и разрыдается над ним. Но, рано ли, поздно ли, это должно было быть, и она вошла в комнату. Рыдания все ближе и ближе подступали ей к горлу, в то время как она своими близорукими глазами яснее и яснее различала его форму и отыскивала его черты, и вот она увидала его лицо и встретилась с ним взглядом.
Он лежал на диване, обложенный подушками, в меховом беличьем халате. Он был худ и бледен. Одна худая, прозрачно белая рука его держала платок, другою он, тихими движениями пальцев, трогал тонкие отросшие усы. Глаза его смотрели на входивших.
Увидав его лицо и встретившись с ним взглядом, княжна Марья вдруг умерила быстроту своего шага и почувствовала, что слезы вдруг пересохли и рыдания остановились. Уловив выражение его лица и взгляда, она вдруг оробела и почувствовала себя виноватой.
«Да в чем же я виновата?» – спросила она себя. «В том, что живешь и думаешь о живом, а я!..» – отвечал его холодный, строгий взгляд.
В глубоком, не из себя, но в себя смотревшем взгляде была почти враждебность, когда он медленно оглянул сестру и Наташу.
Он поцеловался с сестрой рука в руку, по их привычке.
– Здравствуй, Мари, как это ты добралась? – сказал он голосом таким же ровным и чуждым, каким был его взгляд. Ежели бы он завизжал отчаянным криком, то этот крик менее бы ужаснул княжну Марью, чем звук этого голоса.
– И Николушку привезла? – сказал он также ровно и медленно и с очевидным усилием воспоминанья.
– Как твое здоровье теперь? – говорила княжна Марья, сама удивляясь тому, что она говорила.
– Это, мой друг, у доктора спрашивать надо, – сказал он, и, видимо сделав еще усилие, чтобы быть ласковым, он сказал одним ртом (видно было, что он вовсе не думал того, что говорил): – Merci, chere amie, d'etre venue. [Спасибо, милый друг, что приехала.]
Княжна Марья пожала его руку. Он чуть заметно поморщился от пожатия ее руки. Он молчал, и она не знала, что говорить. Она поняла то, что случилось с ним за два дня. В словах, в тоне его, в особенности во взгляде этом – холодном, почти враждебном взгляде – чувствовалась страшная для живого человека отчужденность от всего мирского. Он, видимо, с трудом понимал теперь все живое; но вместе с тем чувствовалось, что он не понимал живого не потому, чтобы он был лишен силы понимания, но потому, что он понимал что то другое, такое, чего не понимали и не могли понять живые и что поглощало его всего.
– Да, вот как странно судьба свела нас! – сказал он, прерывая молчание и указывая на Наташу. – Она все ходит за мной.
Княжна Марья слушала и не понимала того, что он говорил. Он, чуткий, нежный князь Андрей, как мог он говорить это при той, которую он любил и которая его любила! Ежели бы он думал жить, то не таким холодно оскорбительным тоном он сказал бы это. Ежели бы он не знал, что умрет, то как же ему не жалко было ее, как он мог при ней говорить это! Одно объяснение только могло быть этому, это то, что ему было все равно, и все равно оттого, что что то другое, важнейшее, было открыто ему.
Разговор был холодный, несвязный и прерывался беспрестанно.
– Мари проехала через Рязань, – сказала Наташа. Князь Андрей не заметил, что она называла его сестру Мари. А Наташа, при нем назвав ее так, в первый раз сама это заметила.
– Ну что же? – сказал он.
– Ей рассказывали, что Москва вся сгорела, совершенно, что будто бы…
Наташа остановилась: нельзя было говорить. Он, очевидно, делал усилия, чтобы слушать, и все таки не мог.
– Да, сгорела, говорят, – сказал он. – Это очень жалко, – и он стал смотреть вперед, пальцами рассеянно расправляя усы.
– А ты встретилась с графом Николаем, Мари? – сказал вдруг князь Андрей, видимо желая сделать им приятное. – Он писал сюда, что ты ему очень полюбилась, – продолжал он просто, спокойно, видимо не в силах понимать всего того сложного значения, которое имели его слова для живых людей. – Ежели бы ты его полюбила тоже, то было бы очень хорошо… чтобы вы женились, – прибавил он несколько скорее, как бы обрадованный словами, которые он долго искал и нашел наконец. Княжна Марья слышала его слова, но они не имели для нее никакого другого значения, кроме того, что они доказывали то, как страшно далек он был теперь от всего живого.
– Что обо мне говорить! – сказала она спокойно и взглянула на Наташу. Наташа, чувствуя на себе ее взгляд, не смотрела на нее. Опять все молчали.
– Andre, ты хоч… – вдруг сказала княжна Марья содрогнувшимся голосом, – ты хочешь видеть Николушку? Он все время вспоминал о тебе.
Князь Андрей чуть заметно улыбнулся в первый раз, но княжна Марья, так знавшая его лицо, с ужасом поняла, что это была улыбка не радости, не нежности к сыну, но тихой, кроткой насмешки над тем, что княжна Марья употребляла, по ее мнению, последнее средство для приведения его в чувства.
– Да, я очень рад Николушке. Он здоров?

Когда привели к князю Андрею Николушку, испуганно смотревшего на отца, но не плакавшего, потому что никто не плакал, князь Андрей поцеловал его и, очевидно, не знал, что говорить с ним.
Когда Николушку уводили, княжна Марья подошла еще раз к брату, поцеловала его и, не в силах удерживаться более, заплакала.
Он пристально посмотрел на нее.
– Ты об Николушке? – сказал он.
Княжна Марья, плача, утвердительно нагнула голову.
– Мари, ты знаешь Еван… – но он вдруг замолчал.
– Что ты говоришь?
– Ничего. Не надо плакать здесь, – сказал он, тем же холодным взглядом глядя на нее.

Когда княжна Марья заплакала, он понял, что она плакала о том, что Николушка останется без отца. С большим усилием над собой он постарался вернуться назад в жизнь и перенесся на их точку зрения.
«Да, им это должно казаться жалко! – подумал он. – А как это просто!»
«Птицы небесные ни сеют, ни жнут, но отец ваш питает их», – сказал он сам себе и хотел то же сказать княжне. «Но нет, они поймут это по своему, они не поймут! Этого они не могут понимать, что все эти чувства, которыми они дорожат, все наши, все эти мысли, которые кажутся нам так важны, что они – не нужны. Мы не можем понимать друг друга». – И он замолчал.

Маленькому сыну князя Андрея было семь лет. Он едва умел читать, он ничего не знал. Он многое пережил после этого дня, приобретая знания, наблюдательность, опытность; но ежели бы он владел тогда всеми этими после приобретенными способностями, он не мог бы лучше, глубже понять все значение той сцены, которую он видел между отцом, княжной Марьей и Наташей, чем он ее понял теперь. Он все понял и, не плача, вышел из комнаты, молча подошел к Наташе, вышедшей за ним, застенчиво взглянул на нее задумчивыми прекрасными глазами; приподнятая румяная верхняя губа его дрогнула, он прислонился к ней головой и заплакал.
С этого дня он избегал Десаля, избегал ласкавшую его графиню и либо сидел один, либо робко подходил к княжне Марье и к Наташе, которую он, казалось, полюбил еще больше своей тетки, и тихо и застенчиво ласкался к ним.
Княжна Марья, выйдя от князя Андрея, поняла вполне все то, что сказало ей лицо Наташи. Она не говорила больше с Наташей о надежде на спасение его жизни. Она чередовалась с нею у его дивана и не плакала больше, но беспрестанно молилась, обращаясь душою к тому вечному, непостижимому, которого присутствие так ощутительно было теперь над умиравшим человеком.


Князь Андрей не только знал, что он умрет, но он чувствовал, что он умирает, что он уже умер наполовину. Он испытывал сознание отчужденности от всего земного и радостной и странной легкости бытия. Он, не торопясь и не тревожась, ожидал того, что предстояло ему. То грозное, вечное, неведомое и далекое, присутствие которого он не переставал ощущать в продолжение всей своей жизни, теперь для него было близкое и – по той странной легкости бытия, которую он испытывал, – почти понятное и ощущаемое.
Прежде он боялся конца. Он два раза испытал это страшное мучительное чувство страха смерти, конца, и теперь уже не понимал его.
Первый раз он испытал это чувство тогда, когда граната волчком вертелась перед ним и он смотрел на жнивье, на кусты, на небо и знал, что перед ним была смерть. Когда он очнулся после раны и в душе его, мгновенно, как бы освобожденный от удерживавшего его гнета жизни, распустился этот цветок любви, вечной, свободной, не зависящей от этой жизни, он уже не боялся смерти и не думал о ней.
Чем больше он, в те часы страдальческого уединения и полубреда, которые он провел после своей раны, вдумывался в новое, открытое ему начало вечной любви, тем более он, сам не чувствуя того, отрекался от земной жизни. Всё, всех любить, всегда жертвовать собой для любви, значило никого не любить, значило не жить этою земною жизнию. И чем больше он проникался этим началом любви, тем больше он отрекался от жизни и тем совершеннее уничтожал ту страшную преграду, которая без любви стоит между жизнью и смертью. Когда он, это первое время, вспоминал о том, что ему надо было умереть, он говорил себе: ну что ж, тем лучше.
Но после той ночи в Мытищах, когда в полубреду перед ним явилась та, которую он желал, и когда он, прижав к своим губам ее руку, заплакал тихими, радостными слезами, любовь к одной женщине незаметно закралась в его сердце и опять привязала его к жизни. И радостные и тревожные мысли стали приходить ему. Вспоминая ту минуту на перевязочном пункте, когда он увидал Курагина, он теперь не мог возвратиться к тому чувству: его мучил вопрос о том, жив ли он? И он не смел спросить этого.

Болезнь его шла своим физическим порядком, но то, что Наташа называла: это сделалось с ним, случилось с ним два дня перед приездом княжны Марьи. Это была та последняя нравственная борьба между жизнью и смертью, в которой смерть одержала победу. Это было неожиданное сознание того, что он еще дорожил жизнью, представлявшейся ему в любви к Наташе, и последний, покоренный припадок ужаса перед неведомым.
Это было вечером. Он был, как обыкновенно после обеда, в легком лихорадочном состоянии, и мысли его были чрезвычайно ясны. Соня сидела у стола. Он задремал. Вдруг ощущение счастья охватило его.
«А, это она вошла!» – подумал он.
Действительно, на месте Сони сидела только что неслышными шагами вошедшая Наташа.
С тех пор как она стала ходить за ним, он всегда испытывал это физическое ощущение ее близости. Она сидела на кресле, боком к нему, заслоняя собой от него свет свечи, и вязала чулок. (Она выучилась вязать чулки с тех пор, как раз князь Андрей сказал ей, что никто так не умеет ходить за больными, как старые няни, которые вяжут чулки, и что в вязании чулка есть что то успокоительное.) Тонкие пальцы ее быстро перебирали изредка сталкивающиеся спицы, и задумчивый профиль ее опущенного лица был ясно виден ему. Она сделала движенье – клубок скатился с ее колен. Она вздрогнула, оглянулась на него и, заслоняя свечу рукой, осторожным, гибким и точным движением изогнулась, подняла клубок и села в прежнее положение.
Он смотрел на нее, не шевелясь, и видел, что ей нужно было после своего движения вздохнуть во всю грудь, но она не решалась этого сделать и осторожно переводила дыханье.
В Троицкой лавре они говорили о прошедшем, и он сказал ей, что, ежели бы он был жив, он бы благодарил вечно бога за свою рану, которая свела его опять с нею; но с тех пор они никогда не говорили о будущем.
«Могло или не могло это быть? – думал он теперь, глядя на нее и прислушиваясь к легкому стальному звуку спиц. – Неужели только затем так странно свела меня с нею судьба, чтобы мне умереть?.. Неужели мне открылась истина жизни только для того, чтобы я жил во лжи? Я люблю ее больше всего в мире. Но что же делать мне, ежели я люблю ее?» – сказал он, и он вдруг невольно застонал, по привычке, которую он приобрел во время своих страданий.