[음악 재생] 

DOUG 로이드 : 좋아, 그럼 병합 종류는 또 다른 알고리즘 우리는 밖으로 정렬하는 데 사용할 수있는 배열 요소. 우리가 볼 수 그러나, 그것은있어 아주 근본적인 차이 선택 정렬, 버블에서 정렬 및 삽입 정렬 그게 정말 꽤 영리합니다. 

병합의 기본 개념 일종의 작은 배열을 정렬하는 것입니다 다음 그 배열을 결합 함께, 또는 them-- 병합 따라서 정렬 된 순서로 name--. 종류 않습니다 병합 방법 이 도구를 활용하는 것입니다 무엇이다, 재귀 호출 우리는 곧에 대해 이야기 할거야 하지만 우리가 정말 아직 이야기하지 않았습니다. 

여기에 병합 정렬의 기본 생각이다. 어레이의 좌측 절반을 정렬 N을 가정하면 1보다 크다. 그리고 내가 말할 때 무엇을 의미 N을 가정하면, 1은보다 큰 나는 우리가 동의 할 수 있다고 생각 배열하는 경우 단 하나의 요소로 구성되어, 그것은 분류입니다. 우리는 실제로 필요하지 않습니다 여기에 아무것도 할 수 있습니다. 우리는 단지 그것을 정렬 할 선언 할 수 있습니다. 그것은 오직 하나의 요소이다. 

그래서 의사는 다시이며, 어레이의 좌측 절반을 정렬 다음 오른쪽 절반 배열 정렬 다음 함께 두 부분을 병합합니다. 지금, 이미 당신은 수 있습니다 생각, 그것은 종류의 단지 짓이야 당신이 연기하고있는 것처럼 소리 당신은 실제로 아무것도 아닙니다. 당신은 왼쪽으로 정렬 말을하는지 절반은 오른쪽 절반을 정렬 하지만 당신은 이야기하지 않을 내가 어떻게 그 일을하고 있습니다. 

그러나만큼 기억 배열은 하나의 요소이다, 우리는 분류 선언 할 수 있습니다. 그런 다음 우리는 단지 그들을 함께 결합 할 수 있습니다. 그리고 그 사실이다 병합 정렬 뒤에 기본적인 아이디어, 그래서 그것을 파괴하는 것입니다 당신의 배열의 크기는 하나입니다. 그리고 당신은 거기에서 다시. 

일종의 확실히 병합 복잡한 알고리즘. 그리고 또한 리틀 시각화 복잡한. 그래서 희망, 시각화가 나는 당신이 함께 따라 도움이 여기에 있습니다. 그리고 나는 일을 서술하기 위해 최선을 다할 것입니다 이 조금 더를 진행 천천히 다른 것보다 다만 희망이 당신의 머리를 얻을 수 있습니다 병합 정렬 뒤에 아이디어 주변. 

그래서 우리는 같은 배열이 다른 정렬 알고리즘 비디오 당신이 본 한 경우 them-- 여섯 요소 배열. 그리고 여기에 우리의 의사 코드는 일종의 왼쪽 절반은 오른쪽 절반을 정렬 함께 두 부분을 병합합니다. 그럼이 매우 어두운 벽돌 빨간색 보자 배열과 그것의 왼쪽 절반을 정렬 할 수 있습니다. 

당분간 그래서, 우리는거야 오른쪽에있는 물건을 무시합니다. 그것은이있다, 그러나 우리는있어 아직 그 단계에서. 우리 아니에요의 종류 배열의 오른쪽 절반. 우리는 종류의 왼쪽에있어 배열의 절반입니다. 그리고 바로 위하여 조금 더 인 분명, 그래서 참조 할 수 있습니다 어떤 단계로 우리가있어, 나는 전환거야 오렌지에이 세트의 색상. 이제, 우리는 여전히 대해 얘기 원래 배열의 같은 왼쪽 절반. 하지만 내가 할 수있는 의해 그 바라고 있어요 다양한 항목의 색상을 참조하십시오 그것은 좀 더 만들어 줄게 여기에 무슨 일이 일어나고 있는지 취소합니다. 

좋아, 그럼 지금 우리가 세 가지 요소의 배열. 우리는이의 왼쪽 절반을 정렬하려면 어떻게 아직이 단계 배열? 우리는 왼쪽으로 정렬하려는 벽돌 빨간색 array--의 절반 왼쪽 절반의 지금은 오렌지 색깔했습니다. 

음, 우리는 시도 할 수 다시이 과정을 반복합니다. 그래서 우리는 여전히있어 정렬 노력의 중간 전체 배열의 왼쪽 절반. 의 좌측 절반 배열, 난 그냥 갈거야 임의로 결정하는 그 왼쪽 절반 오른쪽 절반보다 작은 것입니다, 이 일이 있기 때문에 세 가지 요소로 구성되어 있습니다. 

그래서 나는 그 말을거야 좌측 절반 어레이의 좌측 절반 단지 요소 다섯 가지입니다. 다섯, 하나의 요소 인 배열, 우리는 그것을 정렬하는 방법을 알고있다. 그리고 다섯은 정렬됩니다. 우리는 단지 그것을 선언 할 것입니다. 그것은 하나의 요소 배열입니다. 

그래서 지금 우리가 분류 한 왼쪽 반쪽은 왼쪽 절반 또는 오히려, 우리가 분류 한 오렌지의 왼쪽 절반. 그래서 지금, 순서에 아직 완료 전체 배열의 왼쪽 절반, 우리는 오른쪽 절반을 정렬 할 필요가 오렌지, 또는이 물건. 우리는 어떻게해야합니까? 음, 우리는 두 요소 배열을 가지고있다. 그래서 우리는 왼쪽 절반을 정렬 할 수 있습니다 두 인 배열의. 두 사람은 하나의 요소이다. 그래서 기본적으로 분류합니다. 그 다음 우리는 오른쪽 절반을 정렬 할 수 있습니다 배열, 하나의 부분. 즉, 기본적으로 일종의이다. 

이것은 이제 처음 우리는 병합 단계에 도달했습니다. 우리는 있지만, 완료 우리는 지금 가지 down-- 내포하고 그것은 까다로운의 일종 재귀와 일이며, 당신은 당신을 유지할 필요 우리가 어디에 대해 머리. 그래서 우리는 왼쪽으로 정렬했습니다 주황색 부분의 절반. 

그리고 지금, 우리는 정렬의 중간에있어 주황색 부분의 오른쪽 절반. 그리고 그 과정에서 우리는 단계에있을 지금에 대한, 함께 두 부분을 병합합니다. 우리는 두 부분을 볼 때 배열, 우리는 둘 중 하나를 참조하십시오. 어떤 요소는 작은? 하나. 

그리고 어떤 요소가 작다? 음, 두 개 또는 아무것도입니다. 그래서 두 가지입니다. 그래서 지금, 그냥 다시 프레임합니다 우리가 상황에있는 경우, 우리가 분류 한 오렌지의 왼쪽 절반 원점의 오른쪽 절반. 나는 색상을 변경했습니다 알고 우리가 어디 다시,하지만입니다. 그리고 그 이유는 내가 이런 짓을 이 프로세스이기 때문이다 아래로 반복, 계속 것. 우리는 왼쪽으로 정렬했습니다 전 오렌지의 절반 과 전 오렌지의 오른쪽 절반. 

이제, 우리는 사람들을 병합해야 함께 너무 두 반쪽. 그것은 우리가에있어 단계입니다. 그래서 우리는 모두를 고려 지금 녹색 요소, 원래 배열의 왼쪽 절반. 그리고 우리는 그 병합 동일한 공정을 사용하여 우리는 두 가지를 병합했다 하나 잠시 전. 

좌측 절반, 작은 왼쪽 절반 요소는 다섯 가지입니다. 가장 작은 요소에 오른쪽 절반은 하나입니다. 그 중 어느 작은? 하나. 

가장 작은 요소에 왼쪽 절반은 다섯이다. 가장 작은 요소에 오른쪽 절반은 두개이다. 작은은 무엇입니까? 두. 그리고 마지막으로 다섯 아무것도, 우리는 다섯 가지를 말할 수있다. 

좋아, 그럼 큰 그림,하자 잠시 휴식을 취할 우리가 어디에서 알아. 우리는에서 시작하는 경우 맨 처음, 우리 지금은 완료 전체 배열 단지 여기 의사 코드의 한 단계. 우리는 분류 한 배열의 왼쪽 절반. 

원래 리콜 순서는 다섯, 둘, 하나. 이 과정을 통해 이동하여 아래 중첩과 반복, 분해 문제를 계속 아래로 더 작은 부분으로, 우리는 지금 완료 의사 코드들 중 하나는 단계 전체 시작 배열. 우리는 그것의 왼쪽 절반을 분류했다. 

그래서 지금의이 정지 할 수 있습니다. 그리고 지금의 오른쪽을 정렬 할 수 있습니다 원래 배열의 절반입니다. 그리고 우리가 그렇게 할거야 같은 반복을 통해 진행 물건을 분해의 과정 다음 그들을 함께 병합. 

그래서 왼쪽 절반 적색, 혹은 좌측 절반 원래의 오른쪽 절반 배열, 내가 말할거야 세 가지입니다. 다시 말하지만, 나는 여기에 일관되고 있어요. 당신은 홀수가있는 경우 요소 수, 그것을 정말인지는 중요하지 않습니다 당신은 왼쪽으로 한 작게 또는 오른쪽으로 한 작은. 

중요한 것은 때마다 당신을 그 수행에서이 문제가 발생 병합, 당신은 일치해야합니다. 당신도 항상 필요 왼쪽 작게 또는 항상 확인해야합니다 우측 작다. 여기에, 나는 항상로 선택했습니다 왼쪽 작게 때 내 배열 또는 내 서브 어레이는 홀수 크기이다. 

세 가지가 하나의 요소이다, 그래서 그것은 정렬됩니다. 우리는 가정을 활용 한 우리의 전 과정에 걸쳐 지금까지. 그래서 지금의 오른쪽을 정렬 할 수 있습니다 우측 절반의 반, 또는 적색의 오른쪽 절반. 

다시 말하지만, 우리는이를 분리해야합니다. 이것은 단일 소자 어레이 아니다. 우리는 분류 선언 할 수 없습니다. 그래서 첫째, 우리는거야 왼쪽 절반을 정렬합니다. 

좌측 절반은 하나의 원소이며, 그래서 기본적으로 일종의이다. 그 다음 우리는 권리를 정렬 할거야 하나의 요소이다 절반. 그것은 기본적으로 분류합니다. 그리고 지금, 우리는 함께 그 두 가지를 병합 할 수 있습니다. 포는 작고, 다음 여섯 작다. 

다시, 무엇을 우리는이 시점에서 짓을 한거야? 우리는 왼쪽으로 정렬했습니다 오른쪽 절반의 절반입니다. 아니면 원래로 돌아 가지 거기 색상, 우리는 왼쪽으로 정렬했습니다 부드러운 빨간색의 절반입니다. 그것은 원래 어두운 벽돌했다 빨간색과 지금은 부드러운 빨간색이다, 아니면 부드러운 빨간색이었다. 

그리고 우리가 분류 한 부드러운 빨간색의 오른쪽 절반. 지금은, 글쎄, 그들은 단지, 다시 녹색있어 우리는 과정을 통해려고하고 있기 때문이다. 그리고 우리는 반복해야 이 반복해서. 

그래서 지금 우리는 사람들을 병합 할 수 있습니다 두 개의 반쪽. 그리고 우리가 여기서 할거야. 검은 선 그러니 좌측 절반을 나누어 이 정렬 부의 우측 절반. 

우리는 작은 값을 비교 array-- 왼쪽 또는 실례합니다, 작은 좌측 절반의 값 오른쪽의 가장 작은 값 절반은 세 가지가 작은 것을 찾을 수 있습니다. 그리고 지금 최적화의 비트, 오른쪽? 아무것도 실제로 없습니다 왼쪽에 왼쪽. 

나머지 아무것도 왼쪽, 그래서 우리는 효율적으로 할 수 있습니다 단지 우리가 선언 할 수 있습니다 난 그러고 그 나머지는 실제로 정렬 그냥 압정 아무것도 없기 때문에,에 에 대해 비교하는 다른. 그리고 우리가 알고있는 오른쪽은 오른쪽으로 정렬됩니다. 

좋아, 그럼 이제 다시 동결하자 우리가 이야기에있는 곳을 파악. 전체 배열에서, 우리는 무엇을 성취 했는가? 우리는 실제로 달성 한 이제 한 단계 두 단계를 반복합니다. 우리는 왼쪽 절반을 분류하고, 우리는 오른쪽 절반을 분류. 

그래서 지금, 남아있는 모든 우리를 위해입니다 함께 두 반쪽을 병합합니다. 그래서 우리는 가장 낮은 값 비교 배열의 각 절반의 요소 차례로 진행합니다. 하나는 세 미만이므로 하나 간다. 

두 세 미만이므로 두 간다. 5 세 미만이므로, 세 간다. 네 5 이하이므로, 네 간다. 이어서 다섯, 여섯 미만인 여섯이 모두 남아 있습니다. 

지금, 나는 알고있다, 그 많은 단계이었다. 그리고 우리는 많이 떠 났어요 우리의 여파로 메모리. 그리고 그 회색 사각형이 무엇인지입니다. 그했다처럼 그리고 그것은 아마 느꼈다 삽입 정렬 이상 많은 거품 종류, 또는 선택 정렬. 

그러나 실제로 때문에 이러한 프로세스의 많은 같은 time--에서 일어나고있는 이는 다시, 우리는거야 뭔가 우리가 이야기 할 때 이야기 미래에 재귀 video-- 실제로이 알고리즘 분명히 근본적 무엇보다 다른 우리는 전에 본 하지만 크게도 더 효율적입니다. 

그 이유는 무엇입니까? 음, 최악의 시나리오, 우리가 N 요소를 분할하려면 다음을 재결합. 그러나 우리는 재결합 할 때 그들은 우리가하고있는 기본적으로 두 배로 증가 작은 배열의 크기입니다. 우리는 하나의 요소의 무리가 배열이 우리 효과적으로 두 요소의 배열로 결합한다. 그리고 우리는 그을 두 소자 어레이 과에 함께 그들을 결합 그래서 네 소자 어레이 및, 등, 등, 우리까지 단일 N 소자 어레이를 가지고있다. 

그러나 얼마나 많은 분열 이 n으로 얻을 걸리나요? 다시 전화 번호부 예를 생각합니다. 얼마나 많은 시간을 우리가 눈물을해야합니까 반에있는 전화 번호부, 얼마나 더 많은 시간은 우리가 전화 번호부를 찢어해야합니까 반, 만약 전화 번호부의 크기 두 배? 단 하나, 바로 거기에? 

그래서 어떤 종류의있다 여기 대수 요소입니다. 그러나 우리는 여전히해야 할 최소 n 개의 모든 요소를​​ 살펴 보자. 최악의 경우의 시나리오에 따라서 종류 N 로그 N에서 실행 병합합니다. 우리는 봐야 N 개의 요소 모두, 우리는 그것들을 결합해야 함께 로그 N 단계의 세트에서. 최선의 시나리오에서, 배열이 완벽하게 정렬됩니다. 잘 됐네요. 그러나 알고리즘을 기반으로 우리는 여기에있다 우리는 여전히 분할과 재결합해야합니다. 이 경우 비록 재결합은 비효율적 가지입니다. 그것은 필요하지 않습니다. 그러나 우리는 여전히 통과 어쨌든 전체 과정. 

최상의 경우에 따라서 최악의 경우에, 이 알고리즘은 N 로그 N 시간에 실행됩니다. 일종의 병합 확실히 조금 까다 롭습니다 다른 주요 정렬 알고리즘보다 우리는 CS50에 대해 이야기 일 뿐이다했습니다 실질적으로 더 강력한. 

만약 그렇다면 당신은 이제까지 발견 기회는 그것을 필요로하는 또는 정렬을 사용하는 대용량 데이터 세트, 점점 재귀의 아이디어의 주위에 당신의 머리 정말 강력한 될 것입니다. 그리고 그것은 만들 것 당신의 프로그램 정말 훨씬 더 효율적 아무것도 대 정렬 병합 사용. 나는 더그 로이드입니다. 이 CS50입니다.