{"id":297424,"date":"2020-01-21T09:00:12","date_gmt":"2020-01-21T09:00:12","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=297424"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=297424","title":{"rendered":"\u041f\u043e\u0447\u0435\u043c\u0443 \u0431\u044b\u0441\u0442\u0440\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0430\u044f? \u041d\u043e\u0432\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043c\u0430\u0441\u0441\u0438\u0432\u0430"},"content":{"rendered":"\n<div class=\"post__text post__text-html\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/484798\/\">\n<p><img decoding=\"async\" align=\"right\" src=\"https:\/\/habrastorage.org\/webt\/-7\/ej\/om\/-7ejomnvmra_demx9nkes8yinge.jpeg\" width=\"320\" alt=\"image\"\/>\u041c\u043d\u043e\u0433\u0438\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u044b \u0434\u0443\u043c\u0430\u044e\u0442, \u0447\u0442\u043e <i><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0\">Quick Sort<\/a><\/i> \u2014 \u0441\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0437 \u0432\u0441\u0435\u0445 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445. \u041e\u0442\u0447\u0430\u0441\u0442\u0438 \u044d\u0442\u043e \u0442\u0430\u043a. \u041d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u043d\u0430 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0445\u043e\u0440\u043e\u0448\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u0435\u0441\u043b\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u0432\u044b\u0431\u0440\u0430\u043d \u043e\u043f\u043e\u0440\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 (<i>\u0442\u043e\u0433\u0434\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <nobr>O (n log n)<\/nobr><\/i>). \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0436\u0435 \u0441\u043b\u0443\u0447\u0430\u0435 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u043a\u0430\u043a \u0438 \u0432 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D1%83%D0%B7%D1%8B%D1%80%D1%8C%D0%BA%D0%BE%D0%BC\">\u043f\u0443\u0437\u044b\u0440\u0438\u043a\u0430<\/a> (<i>\u0442\u043e-\u0435\u0441\u0442\u044c O (n<sup>2<\/sup>)<\/i>). <br clear=\"left\"\/>  \u041f\u0440\u0438 \u044d\u0442\u043e\u043c, \u0435\u0441\u043b\u0438 \u043c\u0430\u0441\u0441\u0438\u0432 \u0443\u0436\u0435 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d, \u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u0441\u0451-\u0440\u0430\u0432\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043d\u0435 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0437\u0430 O (n log n)<\/p>\n<p>  <\/p>\n<p>\u0418\u0441\u0445\u043e\u0434\u044f \u0438\u0437 \u044d\u0442\u043e\u0433\u043e, \u044f \u0440\u0435\u0448\u0438\u043b \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u0432\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0431\u044b \u043b\u0443\u0447\u0448\u0435 \u0437\u0430 quick_sort. \u0418 \u0435\u0441\u043b\u0438 \u043c\u0430\u0441\u0441\u0438\u0432 \u0443\u0436\u0435 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d, \u0442\u043e \u043d\u0435 \u043f\u0440\u043e\u0433\u0430\u043d\u044f\u0442\u044c \u0435\u0433\u043e \u043a\u0443\u0447\u0443 \u0440\u0430\u0437, \u043a\u0430\u043a \u044d\u0442\u043e \u0431\u044b\u0432\u0430\u0435\u0442 \u0443 \u043c\u043d\u043e\u0433\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432.<\/p>\n<blockquote><p>\u00ab\u0414\u0435\u043b\u043e \u0431\u044b\u043b\u043e \u0432\u0435\u0447\u0435\u0440\u043e\u043c, \u0434\u0435\u043b\u0430\u0442\u044c \u0431\u044b\u043b\u043e \u043d\u0435\u0447\u0435\u0433\u043e\u00bb, \u2014 \u0421\u0435\u0440\u0433\u0435\u0439 \u041c\u0438\u0445\u0430\u043b\u043a\u043e\u0432.<\/p><\/blockquote>\n<p>  <\/p>\n<h2>\u0422\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f: <\/h2>\n<p>  <\/p>\n<ol>\n<li>\u041b\u0443\u0447\u0448\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 <nobr>O (n)<\/nobr><\/li>\n<li>\u0421\u0440\u0435\u0434\u043d\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 <nobr>O (n log n)<\/nobr><\/li>\n<li>\u0425\u0443\u0434\u0448\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 <nobr>O (n log n)<\/nobr><\/li>\n<li>\u0412 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u043e\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438<\/li>\n<\/ol>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0414\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u0442\u0435\u043c\u044b, \u043d\u0443\u0436\u043d\u043e \u0437\u043d\u0430\u0442\u044c:<\/b><\/p>\n<div class=\"spoiler_text\">\n<ul>\n<li><a href=\"https:\/\/habr.com\/ru\/post\/422085\/\">\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u044b\u0431\u043e\u0440\u043e\u043c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/post\/281675\/\">\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/post\/181271\/\">\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438<\/a><\/li>\n<\/ul>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u0410 \u0442\u0435\u043f\u0435\u0440\u044c \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043e\u0431\u043e \u0432\u0441\u0451\u043c \u043f\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0443<\/p>\n<p>  <\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043d\u0430\u0448 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u0441\u0435\u0433\u0434\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0431\u044b\u0441\u0442\u0440\u043e, \u043d\u0443\u0436\u043d\u043e \u0447\u0442\u043e\u0431\u044b \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430 \u0431\u044b\u043b\u0430 \u0445\u043e\u0442\u044f \u0431\u044b O (n log n), \u0430 \u0432 \u043b\u0443\u0447\u0448\u0435\u043c \u2014 O (n). \u0412\u0441\u0435 \u043c\u044b \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u043d\u043e \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e \u0432 \u043b\u0443\u0447\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0437\u0430 \u043e\u0434\u0438\u043d \u043f\u0440\u043e\u0445\u043e\u0434. \u041d\u043e \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0435\u0439 \u043f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u0433\u0430\u043d\u044f\u0442\u044c \u043f\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0443 \u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432 \u043d\u0451\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/p>\n<p>  <a name=\"habracut\"><\/a>  <\/p>\n<h3>\u041f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f<\/h3>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u0434\u0432\u0443\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">int* glue(int* a, int lenA, int* b, int lenB) { \tint lenC = lenA + lenB; \tint* c = new int[lenC]; \/\/ \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \tint indx_a = 0; \tint indx_b = 0; \tint i = 0; \t\t\t \tfor (; i &lt; lenC; ++i) { \t\tif (indx_a &lt; lenA) { \t\t\tif (indx_b &lt; lenB) { \/\/ \u041e\u0431\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \t\t\t\tc[i] = (a[indx_a] &lt; b[indx_b]) ?  \t\t\t\t\ta[indx_a++] :  \t\t\t\t\tb[indx_b++]; \t\t\t\tcontinue; \t\t\t} \/\/ \u042d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0435\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043f\u0435\u0440\u0432\u043e\u043c \t\t\twhile (indx_a &lt; lenA) \t\t\t\tc[i++] = a[indx_a++]; \t\t} \t\telse \/\/ \u042d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0435\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u043e \u0432\u0442\u043e\u0440\u043e\u043c \t\t\twhile (indx_b &lt; lenB) \t\t\t\tc[i++] = b[indx_b++]; \t\tbreak; \t} \t\t\t \treturn c; } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u0434\u0432\u0443\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432, \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u0439.<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">void glueDelete(int*& arr, int*& a, int lenA, int*& b, int lenB) { \tif (lenA == 0) { \/\/ \u0435\u0441\u043b\u0438 \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u0443\u0441\u0442\u043e\u0439 \t\tdelete[] a; \/\/ \u0432\u044b\u0441\u0432\u043e\u0431\u043e\u0436\u0434\u0430\u0435\u043c \u043e\u0442 \u043d\u0435\u0433\u043e \u043f\u0430\u043c\u044f\u0442\u044c \t\tarr = b; \/\/ \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u0431\u0443\u0434\u0435\u0442 \u0432\u0442\u043e\u0440\u044b\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c \t\treturn; \t} \tif (lenB == 0) { \/\/ \u0435\u0441\u043b\u0438 \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u0443\u0441\u0442\u043e\u0439 \t\tdelete[] b; \/\/ \u0432\u044b\u0441\u0432\u043e\u0431\u043e\u0436\u0434\u0430\u0435\u043c \u043e\u0442 \u043d\u0435\u0433\u043e \u043f\u0430\u043c\u044f\u0442\u044c \t\tarr = a; \/\/ \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u0431\u0443\u0434\u0435\u0442 \u0432\u0442\u043e\u0440\u044b\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c \t\treturn; \t}  \tint *copy = glue(a, lenA, b, lenB); \/\/ \u0441\u043b\u0438\u0432\u0430\u0435\u043c \tdelete[]a; \/\/ \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e \u043d\u0435\u043d\u0443\u0436\u043d\u044b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b \tdelete[]b; \/\/ \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e \u043d\u0435\u043d\u0443\u0436\u043d\u044b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b \tarr = copy;  \/\/ \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u043c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0424\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0434\u0435\u043b\u0430\u0435\u0442 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0432 \u0433\u0440\u0430\u043d\u0438\u0446\u0430\u0445 \u043e\u0442 lo \u0434\u043e hi<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">void insertionSort(int*& arr, int lo, int hi) { \tfor (int i = lo + 1; i &lt;= hi; ++i) \t\tfor (int j = i; j &gt; 0 && arr[j - 1] &gt; arr[j]; --j) \t\t\tswap(arr[j - 1], arr[j]); } <\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<h2><a name=\"first-version\"><\/a><a href=\"#first-version\">\u041d\u0430\u0447\u0430\u043b\u044c\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 (\u043d\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f):<\/a><\/h2>\n<p>  <\/p>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0435 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u0430 (\u0438 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u0430). \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u0438\u0437 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442. \u0415\u0441\u043b\u0438 \u043e\u043d \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u0430, \u0442\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u0442\u043e\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u043a\u043e\u043d\u0435\u0446 \u0432\u044b\u0431\u043e\u0440\u043a\u0438. \u0418\u043d\u0430\u0447\u0435 \u0435\u0441\u043b\u0438 \u043e\u043d \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u0430, \u0442\u043e \u0434\u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u044d\u0442\u043e\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u043d\u0430\u0447\u0430\u043b\u043e. \u0418\u043d\u0430\u0447\u0435 \u043a\u043b\u0430\u0434\u0451\u043c \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432.<\/p>\n<p>  <\/p>\n<h3>\u041d\u0430 \u0432\u0445\u043e\u0434 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u043c\u0430\u0441\u0441\u0438\u0432 \u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u044d\u0442\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">void FirstNewGeneratingSort(int*& arr, int len) <\/code><\/pre>\n<p>  <\/p>\n<h3>\u0414\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u0438\u0437 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 (\u043d\u0430\u0448\u044b \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u044b \u0438 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u044b) \u0438 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u044b\u0434\u0435\u043b\u0438\u043c \u043f\u0430\u043c\u044f\u0442\u044c<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">int* selection = new int[len &lt;&lt; 1]; \/\/ \u0442\u043e \u0436\u0435 \u0447\u0442\u043e \u0438 new int[len * 2] int left = len - 1; \/\/ \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u044b\u0445 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 int right = len; \/\/ \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u044b\u0445 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432  int* restElements = new int[len]; \/\/ \u0434\u043b\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435 \u0432\u0445\u043e\u0434\u044f\u0442 \u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0443 int restLen = 0; \/\/ \u0438\u043d\u0434\u0435\u043a\u0441 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0434\u043b\u044f \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f <\/code><\/pre>\n<p>  <\/p>\n<p>\u041a\u0430\u043a \u0432\u0438\u0434\u0438\u043c, \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u043c\u044b \u0432\u044b\u0434\u0435\u043b\u0438\u043b\u0438 \u0432 2 \u0440\u0430\u0437\u0430 \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438, \u0447\u0435\u043c \u043d\u0430\u0448 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432. \u042d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u043d\u043e \u043d\u0430 \u0441\u043b\u0443\u0447\u0430\u0439 \u0435\u0441\u043b\u0438 \u0443 \u043d\u0430\u0441 \u043c\u0430\u0441\u0441\u0438\u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d \u0438 \u043a\u0430\u0436\u0434\u044b\u0439 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0431\u0443\u0434\u0435\u0442 \u043d\u043e\u0432\u044b\u043c \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u043e\u043c. \u0422\u043e\u0433\u0434\u0430 \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u043d\u044f\u0442\u0430 \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u0442\u043e\u0440\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0432\u044b\u0431\u043e\u0440\u043a\u0438. \u0418\u043b\u0438 \u0436\u0435 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442 (\u0435\u0441\u043b\u0438 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d \u043f\u043e \u0443\u0431\u044b\u0432\u0430\u043d\u0438\u044e).<\/p>\n<p>  <\/p>\n<h3>\u0414\u043b\u044f \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0443\u0436\u043d\u044b \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c. \u041f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u0431\u0435\u0440\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u0438 \u0432\u0442\u043e\u0440\u043e\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">if (arr[0] &gt; arr[1]) \tswap(arr[0], arr[1]);  selection[left--] = arr[0]; selection[right++] = arr[1]; <\/code><\/pre>\n<p>  <\/p>\n<h3>\u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u0430\u043c\u0430 \u0432\u044b\u0431\u043e\u0440\u043a\u0430<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">for (int i = 2; i &lt; len; ++i) {  \tif (selection[right - 1] &lt;= arr[i]) \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0430 \u043d\u043e\u0432\u044b\u0439 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \t{ \t\tselection[right++] = arr[i]; \t\tcontinue; \t}  \tif (selection[left + 1] &gt;= arr[i]) \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0430 \u043d\u043e\u0432\u044b\u0439 \u043c\u0438\u043d\u0438\u043c\u0443\u043c \t{ \t\tselection[left--] = arr[i]; \t\tcontinue; \t}  \trestElements[restLen++] = arr[i]; \/\/ \u0435\u0441\u043b\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043d\u0435 \u043f\u043e\u043f\u0430\u043b \u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0443, \u043e\u043d \u043f\u043e\u043f\u0430\u0434\u0451\u0442 \u0441\u044e\u0434\u0430 } <\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0438 \u00ab\u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435\u00bb \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0430\u043c \u0435\u0449\u0451 \u043d\u0443\u0436\u043d\u043e \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c. \u041d\u043e \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u0430\u043d\u0438\u043f\u0443\u043b\u044f\u0446\u0438\u0438 \u0441 \u043f\u0430\u043c\u044f\u0442\u044c\u044e.<\/p>\n<p>  <\/p>\n<h3>\u041e\u0441\u0432\u043e\u0431\u043e\u0436\u0434\u0430\u0435\u043c \u043d\u0435\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0443\u044e \u043f\u0430\u043c\u044f\u0442\u044c<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">int selectionLen = right - left - 1; \/\/ \u0434\u043b\u0438\u043d\u0430 \u0432\u044b\u0431\u043e\u0440\u043a\u0438  int* copy = glue(selection + left + 1, selectionLen, nullptr, 0); \/\/ \u0432 \u0434\u0430\u043d\u043e\u043c \u043a\u043e\u043d\u0442\u0435\u043a\u0441\u0442\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u0442 \u0432\u044b\u0431\u043e\u0440\u043a\u0443  delete[] selection; \/\/ \u043c\u044b \u0432\u044b\u0434\u0435\u043b\u044f\u043b\u0438 2 * len \u043f\u0430\u043c\u044f\u0442\u0438, \u0438 \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0435\u0451 \u0447\u0430\u0441\u0442\u044c \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433 \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u0441\u0432\u043e\u0431\u043e\u0436\u0434\u0430\u0435\u043c \u043b\u0438\u0448\u043d\u044e\u044e \u043f\u0430\u043c\u044f\u0442\u044c selection = copy; \/\/ \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u043c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c, \u0442\u0430\u043a \u0447\u0442\u043e \u0442\u0435\u043f\u0435\u0440\u044c selection \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0430\u0449\u0443\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e  delete[] arr; \/\/ \u0434\u0430\u043b\u0435\u0435 \u0431\u0443\u0434\u0435\u0442 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0432\u044b\u0437\u043e\u0432, \u0430 \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0443 \u043d\u0430\u0441 \u0443\u0436\u0435 \u0435\u0441\u0442\u044c, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u0441\u0432\u043e\u0431\u043e\u0434\u0438\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u043e\u0442 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 <\/code><\/pre>\n<p>  <\/p>\n<h3>\u0414\u0435\u043b\u0430\u0435\u043c \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0432\u044b\u0437\u043e\u0432 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0434\u043b\u044f \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438 \u0441\u043b\u0438\u0432\u0430\u0435\u043c \u0438\u0445 \u0441 \u0432\u044b\u0431\u043e\u0440\u043a\u043e\u0439<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">FirstNewGeneratingSort(restElements, restLen); glueDelete(arr, selection, selectionLen, restElements, restLen); <\/code><\/pre>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0412\u0435\u0441\u044c \u043a\u043e\u0434 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 (\u041d\u0435\u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f)<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cs\">void FirstNewGeneratingSort(int*& arr, int len) { \tif (len &lt; 2) \t\treturn;  \tint* selection = new int[len &lt;&lt; 1]; \tint left = len - 1; \tint right = len;  \tint* restElements = new int[len]; \tint restLen = 0;  \tif (arr[0] &gt; arr[1]) \t\tswap(arr[0], arr[1]);  \tselection[left--] = arr[0]; \tselection[right++] = arr[1];  \tfor (int i = 2; i &lt; len; ++i) {  \t\tif (selection[right - 1] &lt;= arr[i]) \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0430 \u043d\u043e\u0432\u044b\u0439 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \t\t{ \t\t\tselection[right++] = arr[i]; \t\t\tcontinue; \t\t}  \t\tif (selection[left + 1] &gt;= arr[i]) \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0430 \u043d\u043e\u0432\u044b\u0439 \u043c\u0438\u043d\u0438\u043c\u0443\u043c \t\t{ \t\t\tselection[left--] = arr[i]; \t\t\tcontinue; \t\t}  \t\trestElements[restLen++] = arr[i]; \/\/ \u0435\u0441\u043b\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043d\u0435 \u043f\u043e\u043f\u0430\u043b \u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0443, \u043e\u043d \u043f\u043e\u043f\u0430\u0434\u0451\u0442 \u0441\u044e\u0434\u0430 \t} \tint selectionLen = right - left - 1; \/\/ \u0434\u043b\u0438\u043d\u0430 \u0432\u044b\u0431\u043e\u0440\u043a\u0438  \tint* copy = glue(selection + left + 1, selectionLen, nullptr, 0); \/\/ \u0432 \u0434\u0430\u043d\u043e\u043c \u043a\u043e\u043d\u0442\u0435\u043a\u0441\u0442\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u0442 \u0432\u044b\u0431\u043e\u0440\u043a\u0443  \tdelete[] selection; \/\/ \u043c\u044b \u0432\u044b\u0434\u0435\u043b\u044f\u043b\u0438 2 * len \u043f\u0430\u043c\u044f\u0442\u0438, \u0438 \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0435\u0451 \u0447\u0430\u0441\u0442\u044c \u0432 \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u0435 \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u0441\u0432\u043e\u0431\u043e\u0436\u0434\u0430\u0435\u043c \u043b\u0438\u0448\u043d\u044e\u044e \u043f\u0430\u043c\u044f\u0442\u044c \tselection = copy; \/\/ \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u043c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c, \u0442\u0430\u043a \u0447\u0442\u043e \u0442\u0435\u043f\u0435\u0440\u044c selection \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0430\u0449\u0443\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e  \tdelete[] arr; \/\/ \u0434\u0430\u043b\u0435\u0435 \u0431\u0443\u0434\u0435\u0442 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0432\u044b\u0437\u043e\u0432, \u0430 \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0443 \u043d\u0430\u0441 \u0443\u0436\u0435 \u0435\u0441\u0442\u044c, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u0441\u0432\u043e\u0431\u043e\u0434\u0438\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u043e\u0442 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \t\t \tFirstNewGeneratingSort(restElements, restLen);  \tglueDelete(arr, selection, selectionLen, restElements, restLen); } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  <\/p>\n<h3>\u041f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 Quick Sort<\/h3>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/df\/7j\/fo\/df7jfo7uodtdpuxqyna-z4gsgr8.png\" alt=\"image\"\/>  <\/p>\n<p>\u041a\u0430\u043a \u0432\u0438\u0434\u0438\u043c, \u044d\u0442\u043e \u0441\u043e\u0432\u0441\u0435\u043c \u043d\u0435 \u0442\u043e, \u0447\u0435\u0433\u043e \u043c\u044b \u0445\u043e\u0442\u0435\u043b\u0438. \u041f\u043e\u0447\u0442\u0438 \u0432 6 \u0440\u0430\u0437 \u0434\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c QuickSort! \u041d\u043e \u0440\u0430\u0437\u044b \u0432 \u044d\u0442\u043e\u043c \u043a\u043e\u043d\u0442\u0435\u043a\u0441\u0442\u0435 \u043d\u0435\u0443\u043c\u0435\u0441\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c, \u0442\u0430\u043a \u043a\u0430\u043a \u0437\u0434\u0435\u0441\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u043c\u0435\u0435\u0442 \u0438\u043c\u0435\u043d\u043d\u043e \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430. \u0412 \u0434\u0430\u043d\u043d\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u0435\u0440\u0432\u044b\u0439 \u0438 \u0432\u0442\u043e\u0440\u043e\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0431\u0443\u0434\u0443\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c. \u0418 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043a\u043e\u043f\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432.<\/p>\n<p>  <\/p>\n<p>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430: <\/p>\n<p>  <\/p>\n<ul>\n<li>\u0425\u0443\u0434\u0448\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439: <nobr><i>O (n <sup>2<\/sup>)<\/i><\/nobr><\/li>\n<li>\u0421\u0440\u0435\u0434\u043d\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439: <nobr><i>O (n <sup>2<\/sup>)<\/i><\/nobr><\/li>\n<li>\u041b\u0443\u0447\u0448\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439: <nobr><i>O (n)<\/i><\/nobr><\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u0425\u043c, \u044d\u0442\u043e \u043d\u0438\u0447\u0435\u043c \u043d\u0435 \u043b\u0443\u0447\u0448\u0435 \u0442\u043e\u0439 \u0436\u0435 \u0441\u0430\u043c\u043e\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438. \u0414\u0430, \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 (\u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439) \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043e\u0447\u0435\u043d\u044c \u0431\u044b\u0441\u0442\u0440\u043e, \u0438 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0435 \u043f\u043e\u043f\u0430\u0434\u0443\u0442 \u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0443.<\/p>\n<p>  <\/p>\n<p>\u041c\u043e\u0436\u0435\u043c \u043f\u043e\u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c. \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043e\u0431\u044b\u0447\u043d\u043e\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/uv\/ix\/j6\/uvixj6zxnviyqztdde_u4fzhg7w.png\" alt=\"image\"\/><\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c \u0441 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0435\u0439:<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">void newGenerationMergeSort(int* a, int lo, int hi, int& minPortion) { \tif (hi &lt;= lo) \t\treturn;  \tint mid = lo + (hi - lo) \/ 2; \tif (hi - lo &lt;= minPortion) { \/\/ \u0435\u0441\u043b\u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0432 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0431\u043b\u043e\u043a, \u0442\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043d\u0430\u0448\u0443 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \t\tint* part = glue(a + lo, hi - lo + 1, nullptr, 0); \/\/ \u043f\u0440\u043e\u0441\u0442\u043e \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u0442 \u043c\u0430\u0441\u0441\u0438\u0432 \t\tFirstNewGeneratingSort(part, hi - lo + 1);  \t\tfor (int i = lo; i &lt;= hi; ++i) { \t\t\ta[i] = part[i - lo]; \t\t} \t\tdelete[] part;  \t\treturn; \t}  \tnewGenerationMergeSort(a, lo, mid, minPortion); \tnewGenerationMergeSort(a, mid + 1, hi, minPortion);  \tint* b = glue(a + lo, mid - lo + 1, a + mid + 1, hi - mid);  \tfor (int i = lo; i &lt;= hi; i++) \t\ta[i] = b[i - lo]; \tdelete[] b; } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  <\/p>\n<h3>\u0414\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0443\u0436\u043d\u0430 \u043a\u0430\u043a\u0430\u044f-\u043d\u0438\u0431\u0443\u0434\u044c \u043e\u0431\u0451\u0440\u0442\u043a\u0430<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">void newMergeSort(int *arr, int length) { \tint portion = log2(length); \/\/ \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0431\u043b\u043e\u043a \u0434\u043b\u044f \u043d\u0430\u0448\u0435\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \tportion *= portion; \t\t \tnewGenerationMergeSort(arr, 0, length - 1, portion); } <\/code><\/pre>\n<p>  <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/qx\/ky\/r5\/qxkyr54rzxuve_lkombyqfqd4ws.png\" alt=\"image\"\/>  <\/p>\n<p>\u0414\u0430, \u043f\u0440\u0438\u0440\u043e\u0441\u0442 \u0432 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0435\u0442\u0441\u044f, \u043d\u043e \u0432\u0441\u0451-\u0436\u0435 \u044d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0435 \u0442\u0430\u043a \u0431\u044b\u0441\u0442\u0440\u043e, \u043a\u0430\u043a Quick Sort. \u0422\u0435\u043c \u0431\u043e\u043b\u0435\u0435 \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u043e O (n) \u043d\u0430 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u0445. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u044d\u0442\u043e\u0442 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0442\u043e\u0436\u0435 \u043e\u0442\u043a\u0438\u0434\u0430\u0435\u043c.<\/p>\n<p>  <\/p>\n<h3>\u0412\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430<\/h3>\n<p>  <\/p>\n<ol>\n<li>\n<p>\u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043d\u0435 \u0431\u044b\u043b\u0430 <nobr>O (n<sup>2<\/sup>)<\/nobr>, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0441\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435 \u043f\u043e\u043f\u0430\u043b\u0438 \u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0443 \u043d\u0435 \u0432 1 \u043c\u0430\u0441\u0441\u0438\u0432 \u043a\u0430\u043a \u0440\u0430\u043d\u0435\u0435, \u0430 \u0440\u0430\u0441\u043a\u0438\u043d\u0443\u0442\u044c \u043d\u0430 2 \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u041f\u043e\u0441\u043b\u0435 \u0447\u0435\u0433\u043e \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u0438\u0445 \u0434\u0432\u0435 \u043f\u043e\u0434\u0447\u0430\u0441\u0442\u0438, \u0438 \u0441\u043b\u0438\u0442\u044c \u0438\u0445 \u0441 \u043d\u0430\u0448\u0435\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u043e\u0439. \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0440\u0430\u0432\u043d\u0443\u044e <i><nobr>O (n log n)<\/nobr><\/i><\/p>\n<\/li>\n<li>\n<p>\u041a\u0430\u043a \u043c\u044b \u0443\u0436\u0435 \u0437\u0430\u043c\u0435\u0442\u0438\u043b\u0438, \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 (\u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439) \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u043c\u043e\u0436\u0435\u0442 \u043d\u0430\u0439\u0442\u0438\u0441\u044c \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e, \u0438 \u044d\u0442\u043e \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e. \u0412\u043e\u0442 \u0442\u0443\u0442 \u0432 \u043f\u043e\u043c\u043e\u0449\u044c \u043d\u0430\u043c \u0432\u0441\u0442\u0443\u043f\u0430\u0435\u0442 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u0431\u0443\u0434\u0435\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c, \u043c\u043e\u0436\u0435\u043c \u043b\u0438 \u043c\u044b \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043f\u043e\u0442\u043e\u0447\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u043d\u0430\u0431\u043e\u0440 \u0438\u0437 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0445, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432\u043e\u0441\u044c\u043c\u0438 \u0432\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0445.<\/p>\n<\/li>\n<\/ol>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u0441\u0435\u0439\u0447\u0430\u0441 \u043d\u0435 \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0442\u043e \u043d\u0435 \u0440\u0430\u0441\u0441\u0442\u0440\u0430\u0438\u0432\u0430\u0439\u0442\u0435\u0441\u044c. \u0422\u0430\u043a \u0438 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c. \u0421\u0435\u0439\u0447\u0430\u0441 \u043d\u0430 \u043a\u043e\u0434\u0435 \u0432\u0441\u0451 \u0441\u0442\u0430\u043d\u0435\u0442 \u044f\u0441\u043d\u043e \u0438 \u0432\u043e\u043f\u0440\u043e\u0441\u044b \u043f\u0440\u043e\u043f\u0430\u0434\u0443\u0442.<\/p>\n<p>  <\/p>\n<h2><a name=\"second-variant\"><\/a><a href=\"#second-variant\">\u041e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u044b\u0439 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430:<\/a><\/h2>\n<p>  <\/p>\n<h3>\u0421\u0438\u0433\u043d\u0430\u0442\u0443\u0440\u0430 \u0442\u0430\u043a\u0430\u044f \u0436\u0435 \u043a\u0430\u043a \u0438 \u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0435<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">void newGenerationSort(int*& arr, int len)<\/code><\/pre>\n<p>  <\/p>\n<p>\u041d\u043e \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0434\u0430\u043d\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442 \u043f\u0435\u0440\u0432\u044b\u043c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u043c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0437\u0432\u0430\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e delete[] (\u043f\u043e\u0447\u0435\u043c\u0443 \u2014 \u043c\u044b \u0443\u0432\u0438\u0434\u0438\u043c \u0434\u0430\u043b\u0435\u0435). \u0422\u043e-\u0435\u0441\u0442\u044c \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u0432\u044b\u0434\u0435\u043b\u044f\u043b\u0438 \u043f\u0430\u043c\u044f\u0442\u044c, \u043c\u044b \u0438\u043c\u0435\u043d\u043d\u043e \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u043b\u0438 \u0430\u0434\u0440\u0435\u0441 \u043d\u0430\u0447\u0430\u043b\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430.<\/p>\n<p>  <\/p>\n<h3>\u041f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0430<\/h3>\n<p>  <\/p>\n<p>\u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u044b\u0439 \u00ab\u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u043d\u0430\u0432\u0451\u0440\u0441\u0442\u044b\u0432\u0430\u043d\u0438\u044f\u00bb (catch up coefficient) \u2014 \u044d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430 \u0441\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c 8. \u041e\u043d\u0430 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043c\u044b \u043f\u043e\u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u043f\u0440\u043e\u0439\u0442\u0438, \u0447\u0442\u043e\u0431\u044b \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u00ab\u043d\u0435\u0434\u043e-\u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u00bb \u0438\u043b\u0438 \u00ab\u043d\u0435\u0434\u043e-\u043c\u0438\u043d\u0438\u043c\u0443\u043c\u00bb \u043d\u0430 \u0441\u0432\u043e\u0451 \u043c\u0435\u0441\u0442\u043e.<\/p>\n<p>  <\/p>\n<pre><code class=\"cpp\">int localCatchUp = min(catchUp, len); \/\/ \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0437\u0430 \u0433\u0440\u0430\u043d\u0438\u0446\u0430\u043c\u0438 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 insertionSort(arr, 0, localCatchUp - 1); \/\/ \u0434\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0435 localCatchUp \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432  if (len &lt;= localCatchUp) \/\/ \u043d\u0430 \u0441\u043b\u0443\u0447\u0430\u0439 \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0430 n &lt;= catchUp \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0430 \u0442\u0430\u043a\u0436\u0435  \treturn; \/\/ \u044d\u0442\u043e \u0431\u0430\u0437\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438 (\u0442\u0430\u043a \u043a\u0430\u043a \u043f\u0440\u0438 \u0442\u0430\u043a\u0438\u0445 \u0440\u0430\u0441\u043a\u043b\u0430\u0434\u0430\u0445 \u043c\u0430\u0441\u0441\u0438\u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d) <\/code><\/pre>\n<p>  <\/p>\n<h3>\u0414\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u0441\u043e\u0437\u0434\u0430\u0451\u043c \u043c\u0430\u0441\u0441\u0438\u0432<\/h3>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u0447\u0442\u043e-\u0442\u043e \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0442\u043e \u0441\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435 \u0432 <a href=\"#first-version\">\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0432\u0435\u0440\u0441\u0438\u0438<\/a><\/p>\n<p>  <\/p>\n<pre><code class=\"cpp\">int* selection = new int[len &lt;&lt; 1]; \/\/ \u0442\u043e \u0436\u0435 \u0447\u0442\u043e \u0438 new int[len * 2] int left = len - 1; \/\/ \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u044b\u0445 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 int right = len;  \/\/ \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u044b\u0445 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 <\/code><\/pre>\n<p>  <\/p>\n<h3>\u0417\u0430\u043f\u043e\u043b\u043d\u0438\u043c \u043f\u0435\u0440\u0432\u044b\u0435 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0432\u044b\u0431\u043e\u0440\u043a\u0438<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">selection[left--] = arr[0]; for (int i = 1; i &lt; localCatchUp; ++i) { \tselection[right++] = arr[i]; } <\/code><\/pre>\n<p>  <\/p>\n<p>\u041d\u0430\u043f\u043e\u043c\u043d\u044e, \u0447\u0442\u043e \u0432 \u043b\u0435\u0432\u0443\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u0443 \u043e\u0442 \u0446\u0435\u043d\u0442\u0440\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u0438\u0434\u0443\u0442 \u043d\u043e\u0432\u044b\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u044b, \u0430 \u0432 \u043f\u0440\u0430\u0432\u0443\u044e \u2014 \u043d\u043e\u0432\u044b\u0435 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u044b<\/p>\n<p>  <\/p>\n<h3>\u0421\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u0435 \u0438\u0437\u0431\u0440\u0430\u043d\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">int restLen = len &gt;&gt; 1; \/\/ \u0442\u043e \u0436\u0435 \u0447\u0442\u043e \u0438 len \/ 2 int* restFirst = new int[restLen]; int* restSecond = new int[restLen];  int restFirstLen = 0; int restSecondLen = 0; <\/code><\/pre>\n<p>  <\/p>\n<h3>\u0422\u0435\u043f\u0435\u0440\u044c, \u0441\u0430\u043c\u043e\u0435 \u0433\u043b\u0430\u0432\u043d\u043e\u0435 \u2014 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u0430\u044f \u0432\u044b\u0431\u043e\u0440\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430<\/h3>\n<p>  <\/p>\n<p>\u0426\u0438\u043a\u043b \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0441 localCatchUp (\u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0443\u0436\u0435 \u043f\u043e\u043f\u0430\u043b\u0438 \u0432 \u043d\u0430\u0448\u0443 \u0432\u044b\u0431\u043e\u0440\u043a\u0443 \u043a\u0430\u043a \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u043e\u0442\u0442\u0430\u043b\u043a\u0438\u0432\u0430\u0442\u044c\u0441\u044f). \u0418 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u0434\u043e \u043a\u043e\u043d\u0446\u0430. \u0422\u0430\u043a \u0447\u0442\u043e \u043f\u043e\u0441\u043b\u0435 \u0432 \u043a\u043e\u043d\u0446\u0435 \u043a\u043e\u043d\u0446\u043e\u0432 \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u0441\u044f \u043b\u0438\u0431\u043e \u0432 \u043c\u0430\u0441\u0441\u0438\u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u043b\u0438\u0431\u043e \u0432 \u043e\u0434\u0438\u043d \u0438\u0437 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u043d\u0435\u0434\u043e-\u0432\u044b\u0431\u043e\u0440\u043a\u0438.<\/p>\n<p>\u0414\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438, \u043c\u043e\u0436\u0435\u043c \u043b\u0438 \u043c\u044b \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0443, \u043c\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0431\u0443\u0434\u0435\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 (\u0438\u043b\u0438 \u0440\u0430\u0432\u0435\u043d) \u043b\u0438 \u043e\u043d \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0443 \u043d\u0430 8 \u043f\u043e\u0437\u0438\u0446\u0438\u0439 \u043b\u0435\u0432\u0435\u0435 (right \u2212 localCatchUp). \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u0442\u0430\u043a, \u0442\u043e \u043c\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u043e\u0434\u043d\u0438\u043c \u043f\u0440\u043e\u0445\u043e\u0434\u043e\u043c \u043f\u043e \u044d\u0442\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0435\u0433\u043e \u043d\u0430 \u043d\u0443\u0436\u043d\u0443\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e. \u042d\u0442\u043e \u0431\u044b\u043b\u043e \u0434\u043b\u044f \u043f\u0440\u0430\u0432\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b, \u0442\u043e-\u0435\u0441\u0442\u044c \u0434\u043b\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0422\u0430\u043a\u0438\u043c \u0436\u0435 \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0434\u0435\u043b\u0430\u0435\u043c \u0441 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b \u0434\u043b\u044f \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445. \u0415\u0441\u043b\u0438 \u043d\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0435\u0433\u043e \u043d\u0438 \u0432 \u043e\u0434\u043d\u0443 \u0441\u0442\u043e\u0440\u043e\u043d\u0443 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u0437\u043d\u0430\u0447\u0438\u0442 \u043a\u0438\u0434\u0430\u0435\u043c \u0435\u0433\u043e \u0432 \u043e\u0434\u0438\u043d \u0438\u0437 rest-\u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432.<\/p>\n<p>  <\/p>\n<p>\u0426\u0438\u043a\u043b \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a:<\/p>\n<p>  <\/p>\n<pre><code class=\"cpp\">for (int i = localCatchUp; i &lt; len; ++i) {  \tif (selection[right - localCatchUp] &lt;= arr[i]) \t{ \t\tselection[right] = arr[i];  \t\tfor (int j = right; selection[j - 1] &gt; selection[j]; --j) \t\t\tswap(selection[j - 1], selection[j]);  \t\t++right; \t\tcontinue; \t}  \tif (selection[left + localCatchUp] &gt;= arr[i]) \t{ \t\tselection[left] = arr[i];  \t\tfor (int j = left; selection[j] &gt;= selection[j + 1]; ++j) \t\t\tswap(selection[j], selection[j + 1]);  \t\t--left; \t\tcontinue; \t}  \tif (i & 1) { \/\/ i - \u043d\u0435\u043f\u0430\u0440\u043d\u043e\u0435 \t\trestFirst[restFirstLen++] = arr[i]; \t} \telse { \t\trestSecond[restSecondLen++] = arr[i]; \t} } <\/code><\/pre>\n<p>  <\/p>\n<p>\u041e\u043f\u044f\u0442\u044c \u0436\u0435, \u0447\u0442\u043e \u0437\u0434\u0435\u0441\u044c \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442? \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u043f\u0438\u0445\u043d\u0443\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u044b. \u041d\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f? \u2014 \u0415\u0441\u043b\u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043a\u0438\u0434\u0430\u0435\u043c \u0435\u0433\u043e \u0432 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u044b. \u041f\u0440\u0438 \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0438 \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u2014 \u043b\u043e\u0436\u0438\u043c \u0435\u0433\u043e \u0432 restFirst \u0438\u043b\u0438 restSecond.<\/p>\n<p>  <\/p>\n<p>\u0421\u0430\u043c\u043e\u0435 \u0441\u043b\u043e\u0436\u043d\u043e\u0435 \u0443\u0436\u0435 \u043f\u043e\u0437\u0430\u0434\u0438. \u0422\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u0441\u043b\u0435 \u0446\u0438\u043a\u043b\u0430 \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0441 \u0432\u044b\u0431\u043e\u0440\u043a\u043e\u0439 (\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 <i>[left + 1]<\/i> \u0438 \u043e\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0432 <i>[right \u2212 1]<\/i>), \u0430 \u0442\u0430\u043a\u0436\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b <i>restFirst <\/i>\u0438 <i>restSecond <\/i>\u0434\u043b\u0438\u043d\u043e\u0439 <i>restFirstLen <\/i>\u0438 <i>restSecondLen <\/i>\u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e.<\/p>\n<p>  <\/p>\n<h3>\u041a\u0430\u043a \u0438 \u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435, \u043f\u0435\u0440\u0435\u0434 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u043c \u0432\u044b\u0437\u043e\u0432\u043e\u043c \u0432\u044b\u0441\u0432\u043e\u0431\u043e\u0436\u0434\u0430\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u043e\u0442 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 (\u0432\u0441\u0435 \u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043c\u044b \u0443\u0436\u0435 \u0438 \u0442\u0430\u043a \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u043b\u0438)<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">delete[] arr; <\/code><\/pre>\n<p>  <\/p>\n<p>\u0423 \u043d\u0430\u0441 \u043c\u0430\u0441\u0441\u0438\u0432 <i>selection<\/i> \u043c\u043e\u0436\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u043c\u043d\u043e\u0433\u043e \u044f\u0447\u0435\u0435\u043a \u043d\u0435\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438. \u041f\u0435\u0440\u0435\u0434 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u043c \u0432\u044b\u0437\u043e\u0432\u043e\u043c \u043d\u0443\u0436\u043d\u043e \u043e\u0441\u0432\u043e\u0431\u043e\u0434\u0438\u0442\u044c \u0435\u0451.<\/p>\n<p>  <\/p>\n<h3>\u041e\u0441\u0432\u043e\u0431\u043e\u0436\u0434\u0430\u0435\u043c \u043d\u0435\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0443\u044e \u043f\u0430\u043c\u044f\u0442\u044c<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">int selectionLen = right - left - 1; \/\/ \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u043b\u0438\u043d\u0430 \u043d\u0430\u0448\u0435\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 int* copy = glue(selection + left + 1, selectionLen, nullptr, 0); \/\/ \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u0432 \u043d\u043e\u0432\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \t\t\t delete[] selection; \/\/ \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c 2 * len \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438 selection = copy; \/\/ \u0432\u043c\u0435\u0441\u0442\u043e \u043d\u0435\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0440\u043e\u0432\u043d\u043e \u0441\u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0430\u043c\u044f\u0442\u0438, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043d\u0443\u0436\u043d\u043e <\/code><\/pre>\n<p>  <\/p>\n<h3>\u0422\u0435\u043f\u0435\u0440\u044c \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u043d\u0430\u0448\u0443 \u0444\u0443\u043a\u043d\u0446\u0438\u044e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0434\u043b\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 restFirst \u0438 restSecond<\/h3>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u0442\u043e\u0433\u043e \u043a\u0430\u043a \u043e\u043d\u043e \u0432\u0441\u0451 \u043e\u0442\u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442, \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043a\u043e\u0434 \u0434\u043e \u043a\u043e\u043d\u0446\u0430. \u041f\u043e\u043a\u0430 \u0447\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u0447\u0442\u043e \u043f\u043e\u0441\u043b\u0435 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0445 \u0432\u044b\u0437\u043e\u0432\u043e\u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u044b restFirst \u0438 restSecond \u0431\u0443\u0434\u0443\u0442 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438.<\/p>\n<pre><code class=\"cpp\">newGenerationSort(restFirst, restFirstLen); newGenerationSort(restSecond, restSecondLen); <\/code><\/pre>\n<p>  <\/p>\n<p>\u0418, \u043d\u0430\u043a\u043e\u043d\u0435\u0446, \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u043b\u0438\u0442\u044c 3 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u0438 \u043d\u0430\u0437\u043d\u0430\u0447\u0438\u0442\u044c \u0435\u0433\u043e \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044e arr.<\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0431\u044b \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u043b\u0438\u0442\u044c <i>restFirst <\/i>+ <i>restSecond <\/i>\u0432 \u043a\u0430\u043a\u043e\u0439-\u043d\u0435\u0431\u0443\u0434\u044c \u043c\u0430\u0441\u0441\u0438\u0432 <i>restFull<\/i>, \u0430 \u043f\u043e\u0442\u043e\u043c \u0443\u0436\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0441\u043b\u0438\u044f\u043d\u0438\u0435 <i>selection <\/i>+ <i>restFull<\/i>. \u041d\u043e \u0434\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0431\u043b\u0430\u0434\u0430\u0435\u0442 \u0442\u0430\u043a\u0438\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c, \u0447\u0442\u043e \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432 <i>selection <\/i>\u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u043c\u0435\u043d\u044c\u0448\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0447\u0435\u043c \u043b\u044e\u0431\u043e\u0439 \u0438\u0437 <i>rest<\/i>-\u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432. \u041f\u0440\u0438\u043f\u0443\u0441\u0442\u0438\u043c \u0432 <i>selection <\/i>\u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f 100 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0432 <i>restFirst <\/i> \u2014 990, \u0430 \u0432 <i>restSecond <\/i> \u2014 1010. \u0422\u043e\u0433\u0434\u0430 \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f <i>restFull <\/i>\u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 990 + 1010 = 2000 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043a\u043e\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u041f\u043e\u0441\u043b\u0435 \u0447\u0435\u0433\u043e \u0434\u043b\u044f \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u0441 <i>selection <\/i> \u2014 \u0435\u0449\u0451 2000 + 100 \u043a\u043e\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0439. \u0418\u0442\u043e\u0433\u043e \u043f\u0440\u0438 \u0442\u0430\u043a\u043e\u043c \u043f\u043e\u0434\u0445\u043e\u0434\u0435 \u0432\u0441\u0435\u0433\u043e \u043a\u043e\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0439 \u0431\u0443\u0434\u0435\u0442 2000 + 2100 = 4100.<\/p>\n<p>\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u0437\u0434\u0435\u0441\u044c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u043b\u0438\u0432\u0430\u0435\u043c <i>selection <\/i>\u0438 <i>restFirst <\/i>\u0432 \u043c\u0430\u0441\u0441\u0438\u0432 <i>selection<\/i>. \u041e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043a\u043e\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f: 100 + 990 = 1090. \u0414\u0430\u043b\u0435\u0435 \u0441\u043b\u0438\u0432\u0430\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u044b <i>selection <\/i>\u0438 <i>restSecond <\/i>\u043d\u0430 \u0447\u0442\u043e \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u043c \u0435\u0449\u0451 1090 + 1010 = 2100 \u043a\u043e\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0439. \u0421\u0443\u043c\u043c\u0430\u0440\u043d\u043e \u0432\u044b\u0439\u0434\u0435\u0442 2100 + 1090 = 3190, \u0447\u0442\u043e \u043f\u043e\u0447\u0442\u0438 \u043d\u0430 \u0447\u0435\u0442\u0432\u0435\u0440\u0442\u044c \u043c\u0435\u043d\u044c\u0448\u0435, \u043d\u0435\u0436\u0435\u043b\u0438 \u043f\u0440\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c \u043f\u043e\u0434\u0445\u043e\u0434\u0435. <\/p>\n<p>  <\/p>\n<h3>\u0424\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u0438\u044f\u043d\u0438\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432<\/h3>\n<p>  <\/p>\n<pre><code class=\"cpp\">int* part2; int part2Len; if (selectionLen &lt; restFirstLen) { \tglueDelete(selection, restFirst, restFirstLen, selection, selectionLen); \/\/ selection += restFirst  \tselectionLen += restFirstLen; \t\t\t\t \tpart2 = restSecond;\t \tpart2Len = restSecondLen; } else { \tglueDelete(part2, restFirst, restFirstLen, restSecond, restSecondLen); \/\/ part2 = restFirst + restSecond \tpart2Len = restFirstLen + restSecondLen; } \t\t\t glueDelete(arr, selection, selectionLen, part2, part2Len); <\/code><\/pre>\n<p>  <\/p>\n<p>\u041a\u0430\u043a \u0432\u0438\u0434\u0438\u043c, \u0435\u0441\u043b\u0438 \u043d\u0430\u043c \u0432\u044b\u0433\u043e\u0434\u043d\u0435\u0439 \u0441\u043b\u0438\u0432\u0430\u0442\u044c <i>selection <\/i>\u0441 <i>restFirst<\/i>, \u0442\u043e \u043c\u044b \u0442\u0430\u043a \u0438 \u0434\u0435\u043b\u0430\u0435\u043c. \u0418\u043d\u0430\u0447\u0435 \u043c\u044b \u0441\u043b\u0438\u0432\u0430\u0435\u043c \u043a\u0430\u043a \u0432 <i>\u00abrestFull\u00bb<\/i><\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0424\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u043a\u043e\u0434 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430:<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">\/\/\/ works only if arr is pointer assigned by new keyword void newGenerationSort(int*& arr, int len) { \tint localCatchUp = min(catchUp, len); \/\/ \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0437\u0430 \u0433\u0440\u0430\u043d\u0438\u0446\u0430\u043c\u0438 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \tinsertionSort(arr, 0, localCatchUp - 1); \/\/ \u0434\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0435 localCatchUp \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432  \tif (len &lt;= localCatchUp) \/\/ \u043d\u0430 \u0441\u043b\u0443\u0447\u0430\u0439 \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0430 n &lt;= catchUp \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \t\treturn; \/\/ \u0430 \u0442\u0430\u043a\u0436\u0435 \u044d\u0442\u043e \u0431\u0430\u0437\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438  \tint* selection = new int[len &lt;&lt; 1]; \/\/ \u0442\u043e \u0436\u0435 \u0447\u0442\u043e \u0438 new int[len * 2] \tint left = len - 1; \/\/ \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u044b\u0445 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \tint right = len;  \/\/ \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u044b\u0445 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \t\t\t \tselection[left--] = arr[0]; \tfor (int i = 1; i &lt; localCatchUp; ++i) { \t\tselection[right++] = arr[i]; \t}  \tint restLen = len &gt;&gt; 1; \tint* restFirst = new int[restLen]; \tint* restSecond = new int[restLen];  \tint restFirstLen = 0; \tint restSecondLen = 0;  \tfor (int i = localCatchUp; i &lt; len; ++i) {  \t\tif (selection[right - localCatchUp] &lt;= arr[i])  \t\t{ \t\t\tselection[right] = arr[i];  \t\t\tfor (int j = right; selection[j - 1] &gt; selection[j]; --j) \t\t\t\tswap(selection[j - 1], selection[j]);  \t\t\t++right; \t\t\tcontinue; \t\t}  \t\tif (selection[left + localCatchUp] &gt;= arr[i]) \t\t{ \t\t\tselection[left] = arr[i];  \t\t\tfor (int j = left; selection[j] &gt;= selection[j + 1]; ++j) \t\t\t\tswap(selection[j], selection[j + 1]);  \t\t\t--left; \t\t\tcontinue; \t\t}  \t\tif (i & 1) { \/\/ i - \u043d\u0435\u043f\u0430\u0440\u043d\u043e\u0435 \t\t\trestFirst[restFirstLen++] = arr[i]; \t\t} \t\telse { \t\t\trestSecond[restSecondLen++] = arr[i]; \t\t} \t} \tdelete[] arr;   \tint selectionLen = right - left - 1; \/\/ \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u043b\u0438\u043d\u0430 \u043d\u0430\u0448\u0435\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \tint* copy = glue(selection + left + 1, selectionLen, nullptr, 0); \/\/ \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u0432 \u043d\u043e\u0432\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \t\t\t \tdelete[] selection; \/\/ \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c 2 * len \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438 \tselection = copy; \/\/ \u0432\u043c\u0435\u0441\u0442\u043e \u043d\u0435\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0440\u043e\u0432\u043d\u043e \u0441\u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0430\u043c\u044f\u0442\u0438, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043d\u0443\u0436\u043d\u043e  \tnewGenerationSort(restFirst, restFirstLen); \tnewGenerationSort(restSecond, restSecondLen);  \tint* part2; \tint part2Len; \tif (selectionLen &lt; restFirstLen) { \t\tglueDelete(selection, restFirst, restFirstLen, selection, selectionLen); \/\/ selection += restFirst  \t\tselectionLen += restFirstLen; \t\t\t\t \t\tpart2 = restSecond;\t \t\tpart2Len = restSecondLen; \t} \telse { \t\tglueDelete(part2, restFirst, restFirstLen, restSecond, restSecondLen); \/\/ part2 = restFirst + restSecond \t\tpart2Len = restFirstLen + restSecondLen; \t} \t\t\t \tglueDelete(arr, selection, selectionLen, part2, part2Len); } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  <\/p>\n<h3>\u0422\u0435\u043f\u0435\u0440\u044c \u0432\u0440\u0435\u043c\u044f \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/h3>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u043a\u043e\u0434 \u0432 Source.cpp:<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">#include &lt;iostream&gt; #include &lt;ctime&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &quot;time_utilities.h&quot; #include &quot;sort_utilities.h&quot;  using namespace std; using namespace rela589n;  void printArr(int* arr, int len) { \tfor (int i = 0; i &lt; len; ++i) { \t\tcout &lt;&lt; arr[i] &lt;&lt; &quot; &quot;; \t} \tcout &lt;&lt; endl; }  bool arraysEqual(int* arr1, int* arr2, int len) { \tfor (int i = 0; i &lt; len; ++i) { \t\tif (arr1[i] != arr2[i]) { \t\t\treturn false; \t\t} \t} \treturn true; }  int* createArray(int length) { \tint* a1 = new int[length];  \tfor (int i = 0; i &lt; length; i++) { \t\ta1[i] = rand(); \t\t\/\/a1[i] = (i + 1) % (length \/ 4); \t}  \treturn a1; }  int* array_copy(int* arr, int length) { \tint* a2 = new int[length]; \tfor (int i = 0; i &lt; length; i++) { \t\ta2[i] = arr[i]; \t}  \treturn a2; }  void tester(int tests, int length) { \tdouble t1, t2;  \tint** arrays1 = new int* [tests]; \tint** arrays2 = new int* [tests];  \tfor (int t = 0; t &lt; tests; ++t) { \/\/ \u043f\u0440\u043e\u0441\u0442\u043e \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \t\tint* arr1 = createArray(length); \t\tarrays1[t] = arr1; \t\tarrays2[t] = array_copy(arr1, length); \t}  \tt1 = getCPUTime(); \tfor (int t = 0; t &lt; tests; ++t) { \t \tquickSort(arrays1[t], 0, length - 1); \t} \tt2 = getCPUTime(); \t \tcout &lt;&lt; &quot;Avg Qsort       time for &quot; &lt;&lt; length &lt;&lt; &quot; elements: &quot; &lt;&lt; (t2 - t1) * 1000 \/ tests &lt;&lt; endl; \t \tint portion = catchUp = 8; \t \tt1 = getCPUTime(); \tfor (int t = 0; t &lt; tests; ++t) { \t\tnewGenerationSort(arrays2[t], length); \t}\t \tt2 = getCPUTime();  \tcout &lt;&lt; &quot;Avg newGenSort  time for &quot; &lt;&lt; length &lt;&lt; &quot; elements: &quot; &lt;&lt; (t2 - t1) * 1000 \/ tests \/\/&lt;&lt; &quot; Catch up coef: &quot;&lt;&lt; portion \t\t&lt;&lt; endl;  \tbool confirmed = true; \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0438\u0434\u0435\u043d\u0442\u0438\u0447\u043d\u044b \u043b\u0438 \u043c\u0430\u0441\u0441\u0438\u0432\u044b \tfor (int t = 0; t &lt; tests; ++t) { \t\tif (!arraysEqual(arrays1[t], arrays2[t], length)) { \t\t\tconfirmed = false; \t\t\tbreak; \t\t} \t} \tif (confirmed) { \t\tcout &lt;&lt; &quot;Confirmed&quot; &lt;&lt; endl; \t} \telse { \t\tcout &lt;&lt; &quot;Review your code! Something wrong...&quot; &lt;&lt; endl; \t} }   int main() { \tsrand(time(NULL));  \tint length; \tdouble t1, t2;  \tcout &lt;&lt; &quot;size: &quot;; \tcin &gt;&gt; length; \t \tint t; \tcout &lt;&lt; &quot;tests: &quot;; \tcin &gt;&gt; t; \ttester(t, length); \tsystem(&quot;pause&quot;);  \treturn 0; } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f Quick Sort, \u0447\u0442\u043e \u0431\u044b\u043b\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0430 \u0434\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043f\u0440\u0438 \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438:<\/b><\/p>\n<div class=\"spoiler_text\">\n<p>\u041d\u0435\u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0440\u0435\u043c\u0430\u0440\u043a\u0430: \u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b \u0438\u043c\u0435\u043d\u043d\u043e \u044d\u0442\u0443 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e quickSort \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0432\u0441\u0451 \u0431\u044b\u043b\u043e \u0447\u0435\u0441\u0442\u043d\u043e. \u0421\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u0430\u044f sort \u0438\u0437 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 algorithm \u0445\u043e\u0442\u044f \u0438 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u0430, \u043d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0432 2 \u0440\u0430\u0437\u0430 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0439 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0439 \u043d\u0438\u0436\u0435.<\/p>\n<p>  <\/p>\n<pre><code class=\"cpp\">\/\/ [min, max] int random(int min, int max) { \treturn min + rand() % ((max + 1) - min); }  void quickSort(int * arr, int b, int e) { \tint l = b, r = e; \tint piv = arr[random(l, r)]; \twhile (l &lt;= r)\t \t{ \t\tfor (; arr[l] &lt; piv; ++l);  \t\tfor (; arr[r] &gt; piv; --r);  \t\tif (l &lt;= r) \t\t\tswap(arr[l++], arr[r--]); \t} \tif (b &lt; r) \t\tquickSort(arr, b, r); \tif (e &gt; l) \t\tquickSort(arr, l, e); } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  <\/p>\n<p>\u0412\u0441\u0435 \u0442\u0435\u0441\u0442\u044b \u0431\u044b\u043b\u0438 \u043f\u0440\u043e\u0432\u0435\u0434\u0435\u043d\u044b \u043d\u0430 \u043c\u0430\u0448\u0438\u043d\u0435 \u043d\u0430 \u043f\u0440\u043e\u0446. <i>Intel core i3 7100u<\/i> \u0438 <i>8\u0413\u0411 \u041e\u0417\u0423<\/i> <\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0440\u0430\u043d\u0434\u043e\u043c\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">a1[i] = rand(); <\/code><\/pre>\n<p>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/kh\/hu\/jo\/khhujosglkjbo3m5i6cc_w9zpca.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/o3\/cr\/vf\/o3crvfqy-0covklmhes08dcwymy.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/d6\/wu\/69\/d6wu690kon7l6bcvxy8gvrl61ym.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/uj\/ov\/yd\/ujovydr2ijvhj9ekoxxg-r0m7ie.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/hr\/jf\/gz\/hrjfgzrbqdt7bxq35gktgbijfac.png\" alt=\"image\"\/>  <\/div>\n<\/div>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0427\u0430\u0441\u0442\u0438\u0447\u043d\u043e \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">a1[i] = (i + 1) % (length \/ 4);<\/code><\/pre>\n<p>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/_k\/ox\/w4\/_koxw4xsxbt2lnpfd5wpmojuen4.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/s_\/xq\/tg\/s_xqtgnerhcgun43cxkh-nbmqsg.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/r2\/s5\/w3\/r2s5w3zzsl8l3qmirmtytdpcsdi.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/cq\/co\/lh\/cqcolhl4sosszhmcxl_ck9axmxi.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/_j\/mv\/56\/_jmv56bfnzwngx5jv_47nno0deq.png\" alt=\"image\"\/>  <\/div>\n<\/div>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">a1[i] = (i + 1);<\/code><\/pre>\n<p>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/ip\/7h\/a_\/ip7ha_kamipmlbbppuvkvj5b2qk.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/c8\/bv\/wl\/c8bvwlsv1e7cudchzdgkl0y9_as.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/e1\/_b\/mk\/e1_bmkjy4_nqceabjv8w1luwmcg.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/6v\/qi\/1x\/6vqi1xvsgsdvnaxdiflwmpm2tdm.png\" alt=\"image\"\/><br \/>  <img decoding=\"async\" width=\"460\" src=\"https:\/\/habrastorage.org\/webt\/rj\/nm\/00\/rjnm00iiaqstfkm7__-9szbyfye.png\" alt=\"image\"\/>  <\/div>\n<\/div>\n<p>  <\/p>\n<h3>\u0412\u044b\u0432\u043e\u0434\u044b<\/h3>\n<p>  <\/p>\n<p>\u041a\u0430\u043a \u0432\u0438\u0434\u0438\u043c, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442, \u0438 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0445\u043e\u0440\u043e\u0448\u043e. \u041f\u043e \u043a\u0440\u0430\u0439\u043d\u0435\u0439 \u043c\u0435\u0440\u0435 \u0432\u0441\u0451 \u0447\u0435\u0433\u043e \u043c\u044b \u0445\u043e\u0442\u0435\u043b\u0438, \u0431\u044b\u043b\u043e \u0434\u043e\u0441\u0442\u0438\u0433\u043d\u0443\u0442\u043e. \u041d\u0430 \u0441\u0447\u0451\u0442 \u0441\u0442\u0430\u0431\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u043d\u0435 \u0443\u0432\u0435\u0440\u0435\u043d, \u043d\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u043b. \u041c\u043e\u0436\u0435\u0442\u0435 \u0441\u0430\u043c\u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c. \u041d\u043e \u043f\u043e-\u0438\u0434\u0435\u0435 \u043e\u043d\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u043b\u0435\u0433\u043a\u043e. \u041f\u0440\u043e\u0441\u0442\u043e \u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u0435\u0441\u0442\u0430\u0445 \u0432\u043c\u0435\u0441\u0442\u043e \u0437\u043d\u0430\u043a\u0430 &gt; \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u2265 \u0438\u043b\u0438 \u0447\u0442\u043e-\u0442\u043e \u0442\u043e\u0433\u043e. <\/p>\n<\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/484798\/\"> https:\/\/habr.com\/ru\/post\/484798\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/484798\/\">\n<p><img decoding=\"async\" align=\"right\" src=\"https:\/\/habrastorage.org\/webt\/-7\/ej\/om\/-7ejomnvmra_demx9nkes8yinge.jpeg\" width=\"320\" alt=\"image\"\/>\u041c\u043d\u043e\u0433\u0438\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u044b \u0434\u0443\u043c\u0430\u044e\u0442, \u0447\u0442\u043e <i><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0\">Quick Sort<\/a><\/i> \u2014 \u0441\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0437 \u0432\u0441\u0435\u0445 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445. \u041e\u0442\u0447\u0430\u0441\u0442\u0438 \u044d\u0442\u043e \u0442\u0430\u043a. \u041d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u043d\u0430 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0445\u043e\u0440\u043e\u0448\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u0435\u0441\u043b\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u0432\u044b\u0431\u0440\u0430\u043d \u043e\u043f\u043e\u0440\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 (<i>\u0442\u043e\u0433\u0434\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <nobr>O (n log n)<\/nobr><\/i>). \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0436\u0435 \u0441\u043b\u0443\u0447\u0430\u0435 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u043a\u0430\u043a \u0438 \u0432 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D1%83%D0%B7%D1%8B%D1%80%D1%8C%D0%BA%D0%BE%D0%BC\">\u043f\u0443\u0437\u044b\u0440\u0438\u043a\u0430<\/a> (<i>\u0442\u043e-\u0435\u0441\u0442\u044c O (n<sup>2<\/sup>)<\/i>). <br clear=\"left\"\/>  \u041f\u0440\u0438 \u044d\u0442\u043e\u043c, \u0435\u0441\u043b\u0438 \u043c\u0430\u0441\u0441\u0438\u0432 \u0443\u0436\u0435 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d, \u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u0441\u0451-\u0440\u0430\u0432\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043d\u0435 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0437\u0430 O (n log n)<\/p>\n<p>  <\/p>\n<p>\u0418\u0441\u0445\u043e\u0434\u044f \u0438\u0437 \u044d\u0442\u043e\u0433\u043e, \u044f \u0440\u0435\u0448\u0438\u043b \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u0432\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0431\u044b \u043b\u0443\u0447\u0448\u0435 \u0437\u0430 quick_sort. \u0418 \u0435\u0441\u043b\u0438 \u043c\u0430\u0441\u0441\u0438\u0432 \u0443\u0436\u0435 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d, \u0442\u043e \u043d\u0435 \u043f\u0440\u043e\u0433\u0430\u043d\u044f\u0442\u044c \u0435\u0433\u043e \u043a\u0443\u0447\u0443 \u0440\u0430\u0437, \u043a\u0430\u043a \u044d\u0442\u043e \u0431\u044b\u0432\u0430\u0435\u0442 \u0443 \u043c\u043d\u043e\u0433\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432.<\/p>\n<blockquote><p>\u00ab\u0414\u0435\u043b\u043e \u0431\u044b\u043b\u043e \u0432\u0435\u0447\u0435\u0440\u043e\u043c, \u0434\u0435\u043b\u0430\u0442\u044c \u0431\u044b\u043b\u043e \u043d\u0435\u0447\u0435\u0433\u043e\u00bb, \u2014 \u0421\u0435\u0440\u0433\u0435\u0439 \u041c\u0438\u0445\u0430\u043b\u043a\u043e\u0432.<\/p><\/blockquote>\n<p>  <\/p>\n<h2>\u0422\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f: <\/h2>\n<p>  <\/p>\n<ol>\n<li>\u041b\u0443\u0447\u0448\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 <nobr>O (n)<\/nobr><\/li>\n<li>\u0421\u0440\u0435\u0434\u043d\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 <nobr>O (n log n)<\/nobr><\/li>\n<li>\u0425\u0443\u0434\u0448\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 <nobr>O (n log n)<\/nobr><\/li>\n<li>\u0412 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u043e\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438<\/li>\n<\/ol>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0414\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u0442\u0435\u043c\u044b, \u043d\u0443\u0436\u043d\u043e \u0437\u043d\u0430\u0442\u044c:<\/b><\/p>\n<div class=\"spoiler_text\">\n<ul>\n<li><a href=\"https:\/\/habr.com\/ru\/post\/422085\/\">\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u044b\u0431\u043e\u0440\u043e\u043c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/post\/281675\/\">\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/post\/181271\/\">\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438<\/a><\/li>\n<\/ul>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u0410 \u0442\u0435\u043f\u0435\u0440\u044c \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043e\u0431\u043e \u0432\u0441\u0451\u043c \u043f\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0443<\/p>\n<p>  <\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043d\u0430\u0448 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u0441\u0435\u0433\u0434\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0431\u044b\u0441\u0442\u0440\u043e, \u043d\u0443\u0436\u043d\u043e \u0447\u0442\u043e\u0431\u044b \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430 \u0431\u044b\u043b\u0430 \u0445\u043e\u0442\u044f \u0431\u044b O (n log n), \u0430 \u0432 \u043b\u0443\u0447\u0448\u0435\u043c \u2014 O (n). \u0412\u0441\u0435 \u043c\u044b \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u043d\u043e \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e \u0432 \u043b\u0443\u0447\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0437\u0430 \u043e\u0434\u0438\u043d \u043f\u0440\u043e\u0445\u043e\u0434. \u041d\u043e \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0435\u0439 \u043f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u0433\u0430\u043d\u044f\u0442\u044c \u043f\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0443 \u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432 \u043d\u0451\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/p>\n<p>  <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-297424","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/297424","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=297424"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/297424\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=297424"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=297424"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=297424"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}