Quicksort

//Time Complexity from O(n log(n)) to O(n^2)
//Space Complexity O(log(n))
//elements less than the middle one go left, greater go right,
//then each part is sorted the same way
void quickSort(int arr[], int first, int last) {
    if (first >= last) {
        return;
    }
    int i = first;
    int j = last;
    int x = arr[first + (last - first) / 2];

    while (i <= j) {
        while (arr[i] < x) {
            i++;
        }
        while (arr[j] > x) {
            j--;
        }
        if (i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    quickSort(arr, first, j);
    quickSort(arr, i, last);
}

void printArray(const char *name, const int arr[], size_t count) {
    printf("%s is {", name);
    for (size_t i = 0; i < count; i++) {
        if (i > 0) {
            printf(", ");
        }
        printf("%d", arr[i]);
    }
    printf("}\n");
}

int items[] = {4, 1, 5, 3, 2};
size_t count = sizeof items / sizeof items[0];

//the sort works in place: a copy keeps items as they are
int sortItems[5];
memcpy(sortItems, items, sizeof items);
quickSort(sortItems, 0, (int)count - 1);
//sortItems is {1, 2, 3, 4, 5}

//the library qsort sorts an array of any type

printArray("items", items, count);
printArray("sortItems", sortItems, count);