Поскольку <=
в вашем коде гарантирует, что одинаковые элементы (в левой и правой половине сортировочного массива) не будут заменены.
А также избегает бесполезных обменов.
if (a[lo] <= a[start_hi]) {
/* The left value is smaller than or equal to the right one, leave them as is. */
/* Especially, if the values are same, they won't be exchanged. */
lo++;
} else {
/*
* If the value in right-half is greater than that in left-half,
* insert the right one into just before the left one, i.e., they're exchanged.
*/
...
}
Предположим, что элемент с одинаковыми значениями (например, "5") в обеих половинах и оператор выше равен <
.
Как показывают комментарии выше, правая цифра «5» будет вставлена перед левой цифрой «5», другими словами, будут заменены элементы с одинаковыми значениями.
Это означает, что сортировка не является стабильной.
А также неэффективно обмениваться элементами с одинаковыми значениями.
Полагаю, причина неэффективности кроется в самом алгоритме.
Этап слияния реализован с использованием сортировки вставкой (как вы знаете, это O (n ^ 2)).
Возможно, вам придется заново реализовать, когда вы сортируете огромные массивы.