정렬 된 목록 병합

4 개의 정렬 된 목록이 있으며 하나의 정렬 된 목록으로 병합하려고합니다.
가장 효율적인 방법은 무엇입니까? 구현을 병렬로 수행 할 수 있다면 플러스입니다.정렬 된 목록 병합

2012-07-04 pythonic

일반적으로 그 목록의 크기는 어느 정도입니까? – unkulunkulu

파이썬이 아닌 C로하고 싶습니다. – pythonic

아, 죄송합니다. 왜 내가 파이썬에 대해 생각했는지 모르겠다. – unkulunkulu

이것은 merge sort의 병합 부분입니다.

각 목록의 머리 부분에있는 네 개의 요소 중 최소한을 가져 와서 출력에 덤프하십시오. 모든 목록이 비어있을 때까지 반복하십시오. min4이 고정 비용이라고 가정하면 이것은 단지 O (N)이 될 것입니다.

목록의 범위와 같은 더 많은 정보가 있다면 아마도 약간 향상시킬 수 있지만 이러한 것들이 점근 적 복잡성에 영향을 미치지 않는다고 생각합니다.

2012-07-04 12:39:03

병합 병행을 병렬화하는 것은 생각만큼 간단하지 않습니다.> 내 대답을 삭제함에 따라 +1하는 것이 의미있는 일입니다. – ArjunShankar

위키 페이지의이 섹션과 해당 섹션의 참고 자료는 다음과 같습니다. http://en.wikipedia.org/wiki/Merge_sort#Parallel_processing – ArjunShankar

답변