Упражнения. 9.5. Напишите процедуру слияния двух упорядоченных списков в один третий список

9.5. Напишите процедуру слияния двух упорядоченных списков в один третий список. Например:

?- слить([2, 5, 6, 6, 8], [1, 3, 5, 9], L).

L = [1, 2, 3, 5, 5, 6, 6, 8, 9]

9.6. Программы сортировки, показанные на рис. 9.2 и 9.3, отличаются друг от друга способом представления списков. Первая из них использует обычное представление, в то время как вторая — разностное представление. Преобразование из одного представления в другое очевидно и может быть автоматизировано. Введите в программу рис. 9.2 необходимые изменения, чтобы преобразовать ее в программу рис. 9.3.

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

9.8. Существует еще одна хорошая идея относительно механизма сортировки списков, позволяющая избавиться от недостатков программы быстрсорт, а именно: разбить список на два меньших списка, отсортировать их, а затем слить вместе. Итак, для того, чтобы отсортировать список L, необходимо

• разбить L на два списка L1 и L2 примерно одинаковой длины;

• произвести сортировку списков L1 и L2,получив списки S1 и S2;

• слить списки S1 и S2, завершив на этом сортировку списка L.

Реализуйте этот принцип сортировки и сравните его эффективность с эффективностью программы быстрсорт.