int _fat_partition_(vetor* vec, int left, int right)

{

    int tamanho = right-left+1;



    if (vec == NULL)

    {

        return -1;

    }



    else if (tamanho < 2)

    {

        return 0;

    }

    if(vec->tamanho < 150) // InsertionSort

    {

        int i, j;

        char* aux;

        for(i = 1; i < vec->tamanho; i++)

        {

            aux = vec->elementos[i].str;

            for(j = i; j>0 && strcmp(aux, vec->elementos[j-1].str) < 0; j--)

            {

                strcpy(vec->elementos[j].str, vec->elementos[j-1].str);

            }

            strcpy(vec->elementos[j].str, aux);

        }

    }

    else

    {

        /* ESCOLHA DE PIVOT - ORDENAÇÃO DOS VALORES LEFT, MIDDLE E RIGHT PARA

        MELHORAR A EFICACIA DO ALGORITMO*/

        int pos = (left+right)/2;

        if(strcmp(vec->elementos[right].str, vec->elementos[left].str) < 0)

        {

            _swap_(vec, left, right);

        }

        if(strcmp(vec->elementos[pos].str, vec->elementos[left].str) < 0)

        {

            _swap_(vec, left, pos);

        }

        if(strcmp(vec->elementos[right].str, vec->elementos[pos].str) < 0)

        {

            _swap_(vec, pos, right);

        }

        /* DUTCH NATIONAL FLAG PROBLEM - 3 way partition*/

        int left_values = left, right_values = right - 1;

        int i;

        for(i = left +1; i <= right_values; )

        {

            if(strcmp(vec->elementos[i].str, vec->elementos[left].str) < 0)

            {

                _swap_(vec, left_values, i);

                left_values++;

            }

            if(strcmp(vec->elementos[i].str, vec->elementos[left].str) > 0)

            {

                _swap_(vec, right_values, i);

                right_values--;

            }

            else

            {

                i++;

            }



        }

        if(left_values > left)

        {

            _fat_partition_(vec, left, left_values-1);

        }

          if(right_values < right)

        {

          _fat_partition_(vec, right_values+1, right);

        }

    }

    return 0;

}