res2001

1. Строки сравниваются с помощью strcmp. Когда вы сравниваете так как у вас в коде, то вы сравниваете значения указателей, а не то на что указывают эти указатели.
2. Чтобы сравнить числа в строковом представлении, строки должны быть одинаковой длинны, т.е. число в строковом представлении с меньшим количеством знаков должно быть дополнено слева нулями до длины большего числа (или дополнять оба числа до какой-то фиксированной длины).
3. Когда у вас "склеено" несколько чисел в строку (каждое из чисел дополнено нулями), то порядок склейки для сортировки должен быть от большей сущности к меньшей. В вашем примере в начале строки должен идти месяц, а затем день.
Только применив все три пункта вы сможете правильно отсортировать подобные строки.
Все это кратко изложил jcmvbkbc в своем ответе.

Но! Вам ничего не мешает сразу же при вводе преобразовывать дату в числовое представление и сортировать уже числа. Это будет гораздо быстрее, чем решать проблемы с текстовой сортировкой.

Как можно было сделать то же самое, но при помощи традиционной обработки массива?

А что такого по вашей ссылке не традиционного в смысле обработки массива? Там вполне традиционные операции.
Видимо вы привыкли, что обращение к элементам массива это arr[i]. Но это лишь один из вариантов.
Вариант примененный в коде по ссылке - инкремент указателей - просто смещает указатель на следующий элемент массива. По идее это должно работать немного быстрее, чем arr[i].
Кстати, принцип работы итераторов в C++ std как раз тот же самый, что использован тут. Так что можете считать, что dest и src это итераторы по строке :-)

Если очень хочется, то можете переписать код с применением индексации. Ничего сложного в таком преобразовании кода нет.

По ссылке, реализован аналог strcat, но эта функция (так же как и функция по ссылке) может приводить к выходам за пределы массива, т.к. тут вообще ни как не контролируется размеры массивов. Было бы интересно реализовать аналоги strncat или strncat_s.

Возвращайте значение iterations из shellsort. В main суммируйте эти значения и в конце находите среднее.

Не заполняются они М.
Если объявляется массив автоматический на стеке без инициализатора, то просто отводится память на стеке (уменьшение/увеличение регистра счетчика стека), никаких "теневых" присваиваний элементам не происходит, элементы массива принимают те значения, которые были в этих ячейках памяти ранее.
То же самое и с динамическим массивом, только механизам выделения памяти другой.
По любому адресу в памяти всегда находится какое-то значение, даже если эта память еще не выделена, просто потому что плашка памяти уже вставлена в материнку и на нее подано питание.

Возможно в вашем случае это и не случайность - вы же не приводите код, которым выделяете память.

Проблема в том, что word у вас массив двойных указателей (**). Тогда как strtok возвращает обычный указатель.
Из-за этого тут
if(word[x] != word[y])
вы сравниваете 2 указателя, а не 2 символа.

Вообще я бы убрал массив word в принципе. Вы сразу можете вызывать polyndrome после того как нашли очередное слово.

Просто так взять и удалить элемент из массива на Си нельзя.
Из статического массива удалить нельзя ничего в принципе - его размер не меняется никогда.
В динамических массивах могут быть варианты:
Вы можете переписать хвост массива, начиная с шестого элемента, на один элемент вперед, т.е. 6 элемент станет 5 и т.д. Но при этом в конце образуется не используемый элемент, избавится от него можно перевыделением массива с помощью realloc, например. Но если это делать, то проще сразу выделить память под новый массив и скопировать весь первый массив, кроме удаляемого элемента, как писал GavriKos.
Другой вариант - помечать подобные не используемые элементы каким-то образом. Либо писать в них какое-то значение, обозначающее для вас, что это не используемый элемент, либо хранить где-то отдельно используемый размер массива (так сделано в std::vector).

Потому что практически все функции могут вернуть ошибку тем или иным образом.
Когда fopen возвращает NULL, то это сигнал, что произошла ошибка при выполнения функции. Вы должны проанализировать значение errno и вывести осмысленное сообщение для пользователя.
https://en.cppreference.com/w/c/io/fopen
Сейчас же у вас на все ошибки выдается единственное сообщение. Вы можете просто вызывать функцию strerror с кодом ошибки errno, чтоб получить нормальное актуальное сообщение об ошибке.
https://en.cppreference.com/w/c/string/byte/strerror

Да. Вводите полный путь к файлу, тогда у вас не будет ошибок связанных с отсутствием файла там где программа пытается его найти. Но это не отменяет правильной обработки ошибок в программе.

Проходите по списку и выводе все строки где дата равна указанной. Все.
Зачем тут сортировка?

В плане сортировки и учитывая, что тема Базы данных, то если смотреть на любую реляционную СУБД, то там сортировка данных достигается за счет создания индексов. Индексы это отдельные (от данных) сущности, т.е. физически порядок данных не меняется, но существует отдельный отсортированный список "указателей на данные".
Справедливости ради стоит сказать, что в СУБД существуют и "кластерные индексы" - это такой индекс, который определяет физическую сортировку данных, т.е. данные физически располагаются в хранилище в порядке указанном в кластерном индексе. Но такой индекс может быть только один для одного набора данных (таблицы), а обычных индексов может быть сколько угодно.

Исходя из вышеописанного вы можете создать индекс по дате поступления. Индекс может представлять собой отсортированный массив указателей на данные, двусвязный список указателей или бинарное дерево указателей или что-то еще. При этом сам список данных останется прежним.
Самый простой вариант массив указателей. Сортировать его можно с помощью стандартного qsort(), поиск производить с помощью бинарного поиска bsearch(). При добавлении или удалении элемента в данные, придется либо полностью перестраивать индекс, либо вручную добавлять/удалять элемент из индекса. В любом случае это будет достаточно затратной операцией.
В двусвязном списке и бинарном дереве со вставкой и удалением все проще и гораздо быстрее. В этом случае проще всего генерировать индекс сразу по мере добавления данных, тогда индекс будет строится вместе со списком данных. Но это соответственно скажется на скорости этих операций. Бинарное дерево лучше реализовывать сразу сбалансированное. Работа с подобными структурами сильно усложнит ваш проект и возможно не совсем вписывается в рамки курсового проекта. Это уже вам решать.