Моя мотивация для этого состоит в том, чтобы написать код сборки Z80 для сортировки таблицы распределения переменных (НДС) серии TI-83 +, но я также заинтересован в этом как в общей проблеме.
Часть НДС, которую я хочу отсортировать, упорядочена в непрерывной памяти, где каждый элемент состоит из данных фиксированного размера, за которыми следует байт размера для имени, а затем имя. Чтобы усложнить ситуацию, по обе стороны от НДС расположены два стека, которые не дают места для маневра для безопасного заполнения выделенной оперативной памятью.
В идеале, я хотел бы использовать O (1) пробел, поскольку у меня есть готовый доступ к 2 768-байтовым буферам непользовательской оперативной памяти. Я также хочу сделать это быстро, так как он может содержать много записей, и это процессор с тактовой частотой 6 МГц (хотя, по сути, 1MIPS - без конвейера команд). Также важно отметить, что каждая запись имеет не менее 8 байтов и не более 15 байтов.
Лучший подход, который мне удалось придумать, основан на передаче блоков памяти, которая не очень быстра на Z80. В прошлом другие реализовывали алгоритм сортировки вставок, но он не был особенно эффективным. Кроме того, хотя я могу (и могу) написать код для сбора в массив и сортировки указателей на все записи, для этого требуется переменное количество места, поэтому мне приходится выделять пользовательскую оперативную память, которой уже не хватает.
Мне кажется, что это смутно напоминает мне о какой-то комбинаторной уловке, с которой я когда-то сталкивался, но за всю мою жизнь хорошее решение этой проблемы уклонилось от меня. Любая помощь будет высоко ценится.