Как MergeSort объекты в ArrayList в JAVA

Question

У меня есть BookData, у которого есть int id и имя String

Кодировка

bookData book = new bookData(1,"Ethan");
bookData book = new bookData(3,"Queen");
bookData book = new bookData(2,"BOB")

ArrayList al = new ArrayList();
al.add(book);

Как я могу использовать сортировку слиянием для сортировки идентификатора в этом ArrayList?

Мне действительно нужно сделать это без использования класса коллекций и класса массивов

Answer 1

Помимо использования правильных синтаксисов, вы можете выполнить List.sort как:

List<BookData> al = new ArrayList<>(); // initialise as you will ; renamed class name as 'BookData'
al.sort(Comparator.comparingInt(bookData::getId));

, который самостоятельно выполняет итеративную сортировку слиянием.Из примечания к его реализации -

Эта реализация представляет собой стабильную, адаптивную итеративную сортировку слиянием , которая требует гораздо меньше, чем n lg (n) сравнений, когда входной массив частично отсортирован, в то время какпредлагая производительность традиционной сортировки слиянием, когда входной массив упорядочен случайным образом.Если входной массив почти отсортирован, реализация требует приблизительно n сравнений.Требования к временному хранилищу варьируются от небольшой константы для почти отсортированных входных массивов до n / 2 ссылок на объекты для произвольно упорядоченных входных массивов.