Java - Я на самом деле написал алгоритм сортировки слияния?

Question

Или это какой-то близкий вариант?

К счастью, это довольно быстро, я могу сортировать список из 15 000 000 элементов за 20 секунд (конечно, это зависит от скорости локального процессора).

Я рассмотрел исходный код для «реальных» реализаций слияния и ни один из них не удаленно выглядел как мой код. Алгоритм должен быть более или менее одинаковым (я думаю). Он использует вспомогательный метод, который объединяет два отсортированных списка в один объединенный отсортированный список. Затем метод MergeSort рекурсивно разбивает несортированный список пополам, пока он не попадает в списки с одним размером элемента, а затем объединяет их по мере того, как он завершает стек со вспомогательным методом, указанным ранее.

import java.util.*; 

public class MergeSort{ 

    public static void main(String []args){ 
     List a = fillListRand(150); 
     List sorted = mergeSort(a); 
     System.out.println("Done."); 
     System.out.println("Unsorted: " + a.toString()); 
     System.out.println("Sorted: " + sorted.toString()); 
    } 

    public static List mergeSort(List unsorted) { 
     if(unsorted.size() == 1) 
      return unsorted; 

     return mergeLists(mergeSort(unsorted.subList(0,unsorted.size()/2)), 
          mergeSort(unsorted.subList(unsorted.size()/2,unsorted.size()))); 
    } 

    public static List mergeLists(List a, List b) { 
     List newList = new ArrayList(); 
     int aIndex = 0; 
     int bIndex = 0; 

     while((aIndex < a.size()) && (bIndex < b.size())) { 
      if((int)a.get(aIndex) > (int)b.get(bIndex)) { 
       newList.add(b.get(bIndex)); 
       bIndex++; 
      } 

      else { 
       newList.add(a.get(aIndex)); 
       aIndex++; 
      } 
     } 

     if(aIndex >= a.size()) 
      newList.addAll(b.subList(bIndex,b.size())); 

     else if (bIndex >= b.size()) 
      newList.addAll(a.subList(aIndex,a.size())); 

     return newList; 
    } 

    public static List fillListRand(int num) { 
     List newList = new ArrayList(); 
     Random r = new Random(); 
     for(int i = 0; i < num; i++) { 
      newList.add(r.nextInt(100)); 
     } 
     return newList; 
    } 
} 

Спасибо!

Answer 1

Да, это сортировка слияния, поскольку она делит элементы примерно пополам, сортирует каждую половину и объединяется. Время работы - O (n log n), а дополнительное пространство - O (n). Основное различие, о котором вы говорили, в том, что в других реализациях слияния часто есть указатели слева, среднего и правого. Вы просто скрыли индексирующую арифметику за звонками до .subList, что, возможно, более элегантно, но, возможно, менее эффективно в зависимости от того, как реализована .subList. Если log n повторных вызовов на .subList приводит к цепочке из log n объектов, то каждый доступ к элементу будет стоить O (log n), когда он прокладывает себе путь через цепочку. К счастью, каждый элемент доступен только один раз таким образом, поэтому асимптотическое общее время работы не изменится с O (n log n). (Кажется более вероятным, что вызов .subList в списке, построенном с .subList, будет высвечиваться средним объектом, так что глубина указателя останется 0 (1).)