в parray_sort во внешнем цикле попробуй идти не от 0 до pa->nelems-1, а от pa->nelems-1 до 1, не нужно будет вычислять (pa->nelems - 1) - i и внутренний цикл будет проще и понятнее записан.