слишком медленный хоаr

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

void hoarasort(int *arr, int left, int right)
{

int i = left, j = right, x = 0;
int key = arr[(left + right) / 2];

do {
   while (arr[i] < key)
     i++;
   while (arr[j] > key)
     j--;

   if (i <= j)
   {
     if (i < j)
     {
      x = arr[i];
      arr[i] = arr[j];
      arr[j] = x;
     }
     i++;
     j--;
   }
} while (i <= j);

if (i < right)
   hoarasort(arr, i, right);
if (left < j)
   hoarasort(arr, left, j);
}

int main ()
{
  int n = 0;
  cin >> n;
  int *arr;
  arr = new int [n];

  for (int i=0; i<n; i++)
  cin >> arr[i];

  int right = n-1;
  int left = 0;

  hoarasort(arr, left, right);

  for (int i=0; i<n; i++)
  cout << arr[i] << " ";
}