병합 정렬 된 목록

Question

나는 n 개의 요소가있는 j 개의 정렬 된 목록을 병합하기위한 분할 및 정복 알고리즘을 고안하려고 노력하고 있습니다. 나는이 문제를 어떻게 작은 하위 문제로 나눌 지 모른다. 보다 효율적인 병합 알고리즘을 다음과 같이 사용하고자합니다.

처음 두 목록을 병합합니다. 결과 목록을 세 번째 목록과 병합하십시오. 결과 목록을 O (j * jn)를 취하는 네 번째 목록과 병합하십시오.

Answer 1

유

while(n!=1) 
    for i=0 to n/2 
     merge list(i) with list list(n) 
    n = n/2 

에게 (J의 * 로그 (J) n)이 시간 O에서 u는 쌍으로 전체 그룹을 병합 그런 식으로 그것을 할 수 있습니다, 다음 쌍 등

Answer 2

확실하지 않음에 쌍 왜 이것을 달성하기 위해 분열과 정복이 필요한가? 당신은 단지 다음이 될 것이다 큰 목록을 정렬하는 일종의 내장 사용하는 정렬되지 않은 하나 개의 큰 목록을 만들 수 O (요 * 로그인 (요))

List<int> returnList(List<List<int>> lists) 
    { 
     List<int> ret = new List<int>(); 
     for(int i=0;i<lists.Length;i++) 
     { 
      for(int j=0;j<lists;j++) 
      { 
       ret.Add(lists[i][j]);    
      } 
     } 
     ret.Sort(); 
    } 

Answer 3

이 표준 병합 정렬 다르지 않습니다. 정렬되지 않은 항목이있는 크기 jn 목록을 고려하십시오. 크기가 jn 인 항목의 log(n) 병합 정렬을 수행 한 후에는 j의 각 목록에 n 개의 항목이있는 정렬 된 목록을 갖게됩니다. 그래서 병합 정렬로 계속해서 문제를 해결하십시오.

나누기 및 정복 알고리즘 인 병합 정렬을 조회하고 이해하십시오. 그러면이 문제를 쉽게 해결할 수 있습니다.