#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define countof(array) (sizeof(array) / sizeof((array)[0]))

// Фтыкает value в нужное место массива array с текущим размером из length.
// Кладет в length новый размер массива, возвращает индекс нового элемента.
// Никаких реаллокаций не делает, подразумевая, что памяти хватит, чтобы
// увеличить массив хотя бы на один элемент.
static int insert(int value, int *array, int *length)
{
    int first = 0;
    int last = *length - 1;
    int pos = -1;

    // Специальный случай bsearch. Скукоживаем диапазон в поисках правильной
    // позиции, в которую нужно записать значение.
    while (first <= last) {
        // Вычисляем индекс элемента в середине диапазона.
        int i = first + (last - first) / 2;

        if (value < array[i]) {
            // Фтыкаемое значение меньше текущего элемента. Ограничиваем
            // диапазон сверху предыдущим элементом.
            last = i - 1;
        } else if (value > array[i]) {
            // Фтыкаемое значение больше текущего элемента. Ограничиваем
            // диапазон снизу.
            first = i + 1;
        } else {
            // В массиве нашелся элемент с точно таким же значением.
            pos = i;
            break;
        }
    }

    if (pos < 0) {
        // Если мы не нашли такой же элемент в массиве, тогда first равен
        // позиции, где мы ожидали этот элемент увидеть.
        pos = first;
    }

    // Подвигаем хвост массива, чтобы освободить место под элемент.
    memmove(array + pos + 1, array + pos, (size_t) (*length - pos) * sizeof(array[0]));

    // Фтыкаем элемент на его законное место.
    array[pos] = value;

    // Обновляем length.
    ++(*length);

    return pos;
}

int main(void)
{
    srand((unsigned) time(NULL));

    int array[128];
    int length = 0;

    // Зополняем массиф.
    while (length < (int) countof(array))
    {
        int value = rand() % 300;
        int pos = insert(value, array, &length);
        printf("Inserted %d at %d\n", value, pos);
    }

    // Выводем массиф.
    for (int i = 0; i < length; ++i) {
        printf("%3d: %-11d\n", i, array[i]);

        if (i + 1 < length && array[i] > array[i + 1]) {
            printf("Pizdariki!\n");
            exit(1);
        }
    }
}