Какая реализация лучше для быстрой сортировки и почему? ⇐ C++

[Anonymous]

Схема разделения Хоара:

Код: Выделить всё

void quickSort(vector& arr, int low, int high) {
if (low >= high) return;
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot);
quickSort(arr, pivot + 1, high);
}

int partition(vector& arr, int low, int high) {
int pivot = arr[low];
int left = low - 1;
int right = high + 1;

while (1) {
left++;
while (arr[left] < pivot){
left++;
}

right--;
while (arr[right] > pivot){
right--;
}

if (left >= right){
return right;
}
swap(arr[left], arr[right]);
}
}

против
Схемы разделов Lomuto:

Код: Выделить всё

void quickSort(vector& arr, int low, int high) {
if (low >= high) return;
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}

int partition(vector& arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);

for (int j = low; j  low) j--;
else break;
}
if(i < j) swap(arr[i], arr[j]);
else break;
}
swap(arr[j], arr[pivot]);
return j;
}

Последний код был моей реализацией, которая превышала время для некоторых тестовых случаев, которые я не могу увидеть, но два приведенных выше примера работали, на которые я ссылался из Интернета. Почему?
Какой из этих трех кодов лучше с точки зрения временной и пространственной сложности и почему?

Подробнее здесь: https://stackoverflow.com/questions/793 ... rt-and-why