MergeSort 값이 잘못 출력되었습니다.

Question

저는 100 크기의 LinkedList에 mergesort를 구현하려고합니다. 많은 읽기와 비교를 한 후에 알고리즘이 올바르다 고 보이지만 잘못 입력 한 것으로 보입니다.

public class MergeSort 
{ 
static LinkedList<Integer> list = new LinkedList<>(); 
public static void main(String[] args) 
{   
    //add ints to list 
    for(int i = 0;i < 100; i++) 
    { 
     list.add(roll()); 
    } 
    //print list as a table 
    for(int i = 0; i < 100; i++) 
    { 
     if((i + 1) % 10 == 0) 
     { 
      System.out.println(list.get(i) + "\t"); 
     } 
     else 
     { 
      System.out.print(list.get(i) + "\t"); 
     } 
    } 
    mergeSort(list); 

    //put some space between printed tables 
    System.out.println(""); 
    System.out.println(""); 

    //print list after sort 
    for(int i = 0; i < 100; i++) 
    { 
     if((i + 1) % 10 == 0) 
     { 
      System.out.println(list.get(i) + "\t"); 
     } 
     else 
     { 
      System.out.print(list.get(i) + "\t"); 
     } 
    } 
} 
/* 
Performs the mergesort 
*/ 
static void mergeSort(LinkedList<Integer> ll) 
{ 
    if(ll.size() > 1) 
    { 
     int tmp = ll.size()/2; 

     //this whole bit is to change the sublist of List type to a LinkedList 
     List leftTmp = ll.subList(0, tmp); 
     List rightTmp = ll.subList(tmp, ll.size()); 

     LinkedList<Integer> left = new LinkedList<>(); 
     LinkedList<Integer> right = new LinkedList<>(); 

     left.addAll(leftTmp); 
     right.addAll(rightTmp); 

     mergeSort(left); 
     mergeSort(right); 

     merge(ll, left, right); 
    } 
} 
//performs the merge on the sublists from mergeSort 
static void merge(LinkedList<Integer> o, LinkedList<Integer> l, LinkedList<Integer> r) 
{ 
    int combo = l.size() + r.size(); 

    int t = 0; 
    int tL = 0; 
    int tR = 0; 

    while(t < combo) 
    { 
     if((tL < l.size() && tR < r.size())) 
     { 
      if(l.get(tL) < r.get(tR)) 
      { 
       o.set(t, tL); 
       t++; 
       tL++; 
      } 
      else 
      { 
       o.set(t, tR); 
       t++; 
       tR++; 
      } 
     } 
     else 
     { 
      if(tL >= l.size()) 
      { 
       while(tR < r.size()) 
       { 
        o.set(t, tR); 
        t++; 
        tR++; 
       } 
      } 
      if(tR >= r.size()) 
      { 
       while(tL < l.size()) 
       { 
        o.set(t, tL); 
        t++; 
        tL++; 
       } 
      } 
     } 
    } 
} 
/* 
Performs a random roll for use in the list 
Returns a random integer 
*/ 
public static int roll() 
{ 
    double d = Math.random() * 1000.0; 
    int i = (int)d; 
    return i; 
} 
} 

아래 코드는이 소음이

642 495 716 307 716 893 681 617 150 761 
350 87 564 566 301 40 951 350 804 961 
406 864 161 408 600 434 218 142 808 426 
623 77 935 370 924 881 615 193 518 798 
955 479 810 778 901 375 656 103 526 583 
352 459 768 839 925 885 267 443 497 65 
982 688 812 227 242 479 819 271 681 48 
364 844 315 438 623 781 649 332 918 690 
275 891 927 516 897 504 127 581 111 704 
492 942 525 110 102 915 33 881 331 256 


0 0 1 2 3 1 2 3 4 5 
4 5 6 7 6 7 8 8 9 9 
10 10 11 12 13 14 15 11 12 13 
14 15 16 17 16 17 18 18 19 19 
20 21 22 23 20 21 22 23 24 25 
24 25 26 26 27 28 29 27 28 29 
30 30 31 32 33 31 32 33 34 35 
34 35 36 37 36 37 38 38 39 39 
40 40 41 41 42 43 44 45 46 47 
42 43 44 45 46 47 48 49 48 49 

사람이 이유를 말해 줄 수 출력? 나는 여러 번 그것을 보았고 그것을 이해할 수 없다. 그것은 같은 값조차 가지고 있지 않으며, 그것들을 바꾸고, KINDOF는 그것들을 올바른 순서로 놓습니다. 나는 어디로 잘못 갔는가?

Answer 1

o.set(t, tL)을 쓸 때 왼쪽 목록의 색인을 병합 된 목록의 값으로 할당합니다. 왼쪽 목록의 값을 병합 된 목록 인 o.set(t, l.get(tL))에 할당하려고합니다.

그래서 "정렬 된"목록에서 다른 번호를 얻었습니다. 원래 값 대신 색인이 있습니다.