/* Copyright (c) 2009 Nicira, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <config.h>

#include "sort.h"

#include "random.h"

static size_t
partition(size_t p, size_t r,
          int (*compare)(size_t a, size_t b, void *aux),
          void (*swap)(size_t a, size_t b, void *aux),
          void *aux)
{
    size_t x = r - 1;
    size_t i, j;

    i = p;
    for (j = p; j < x; j++) {
        if (compare(j, x, aux) <= 0) {
            swap(i++, j, aux);
        }
    }
    swap(i, x, aux);
    return i;
}

static void
quicksort(size_t p, size_t r,
          int (*compare)(size_t a, size_t b, void *aux),
          void (*swap)(size_t a, size_t b, void *aux),
          void *aux)
{
    size_t i, q;

    if (r - p < 2) {
        return;
    }

    i = random_range(r - p) + p;
    if (r - 1 != i) {
        swap(r - 1, i, aux);
    }

    q = partition(p, r, compare, swap, aux);
    quicksort(p, q, compare, swap, aux);
    quicksort(q, r, compare, swap, aux);
}

void
sort(size_t count,
     int (*compare)(size_t a, size_t b, void *aux),
     void (*swap)(size_t a, size_t b, void *aux),
     void *aux)
{
    quicksort(0, count, compare, swap, aux);
}