[MUSIC CHÆ I] 

DOUG LLOYD: OK, do đó, một hợp nhất sort là thuật toán nào khác rằng chúng ta có thể sử dụng để sắp xếp ra các yếu tố của một mảng. Tuy nhiên, như chúng ta sẽ thấy, nó có một sự khác biệt rất cơ bản từ sắp xếp chọn, bong bóng sắp xếp, và sắp xếp chèn mà làm cho nó thực sự rất thông minh. 

Ý tưởng cơ bản đằng sau hợp nhất sort để sắp xếp mảng nhỏ hơn và sau đó kết hợp những mảng với nhau, hoặc hợp nhất them-- do đó name-- trong thứ tự sắp xếp. Cách mà hợp nhất phân loại hiện đây là bằng cách tận dụng một công cụ được gọi là đệ quy, đó là những gì chúng ta sẽ nói về sớm, nhưng chúng tôi đã không thực sự nói về chưa. 

Dưới đây là những ý tưởng cơ bản đằng sau sắp xếp hợp nhất. Sắp xếp một nửa trái của mảng, giả sử n là lớn hơn 1. Và những gì tôi có nghĩa là khi tôi nói giả sử n là lớn hơn 1 là, Tôi nghĩ rằng chúng ta có thể đồng ý rằng nếu một mảng chỉ bao gồm một yếu tố duy nhất, nó được sắp xếp. Chúng tôi không thực sự cần để làm bất cứ điều gì với nó. Chúng tôi chỉ có thể khai báo nó sẽ được sắp xếp. Nó chỉ là một yếu tố duy nhất. 

Vì vậy, các mã giả, một lần nữa, là sắp xếp các nửa trái của mảng, sau đó sắp xếp đúng một nửa mảng, sau đó hợp nhất hai nửa lại với nhau. Bây giờ, đã có thể là bạn suy nghĩ, nó loại chỉ Nghe có vẻ như bạn đang đặt ra the-- bạn không thực sự làm bất cứ điều gì. Bạn đang nói sắp xếp bên trái một nửa, sắp xếp một nửa bên phải, nhưng bạn không nói tôi làm thế nào bạn đang làm nó. 

Nhưng hãy nhớ rằng miễn là một mảng là một yếu tố duy nhất, chúng ta có thể khai báo nó được sắp xếp. Sau đó, chúng tôi chỉ có thể kết hợp chúng lại với nhau. Và đó thực sự là Ý tưởng cơ bản đằng sau sắp xếp hợp nhất, là để phá vỡ nó xuống để mảng của bạn có kích thước một. Và sau đó bạn xây dựng lại từ đó. 

Hợp nhất phân loại là chắc chắn một thuật toán phức tạp. Và nó cũng là một chút phức tạp để hình dung. Vì vậy, hy vọng, sự hình dung rằng tôi có ở đây sẽ giúp bạn theo cùng. Và tôi sẽ cố gắng hết sức mình để tường thuật những điều và tiến hành thông qua nhiều hơn một chút chậm hơn so với những người khác chỉ để hy vọng có được đầu của bạn xung quanh ý tưởng đằng sau sắp xếp hợp nhất. 

Vì vậy, chúng tôi có cùng một mảng như phân loại video thuật toán khác nếu bạn đã nhìn thấy them-- một mảng sáu yếu tố. Và mã giả của chúng tôi ở đây là loại nửa bên trái, sắp xếp một nửa bên phải, hợp nhất hai nửa lại với nhau. Vì vậy, chúng ta hãy gạch đỏ này rất tối mảng và sắp xếp các nửa trái của nó. 

Vì vậy, trong thời gian này, chúng ta sẽ để bỏ qua các công cụ bên phải. Nó ở đó, nhưng chúng tôi không phải ở đó bước nào. Chúng tôi không phải lúc sắp xếp các nửa bên phải của mảng. Chúng tôi đang ở loại trái một nửa của mảng. Và chỉ vì lợi ích của việc nhiều hơn một chút rõ ràng, vì vậy tôi có thể tham khảo với những gì chúng tôi bước vào, Tôi sẽ chuyển đổi Màu sắc của bộ này để màu da cam. Bây giờ, chúng tôi vẫn nói về các cùng một nửa bên trái của mảng ban đầu. Nhưng tôi hy vọng rằng bằng việc có thể tham khảo các màu sắc của các mặt hàng khác nhau, nó sẽ làm cho nó nhiều hơn một chút rõ ràng những gì đang xảy ra ở đây. 

OK, vì vậy bây giờ chúng ta có một ba phần tử mảng. Làm thế nào để chúng tôi sắp xếp nửa trái này mảng, mà vẫn là bước này? Chúng tôi đang cố gắng để sắp xếp bên trái một nửa của gạch array-- đỏ nửa bên trái đó Bây giờ tôi đã có màu cam. 

Vâng, chúng ta có thể thử và lặp lại quá trình này một lần nữa. Vì vậy, chúng tôi vẫn đang trong giữa cố gắng sắp xếp nửa bên trái của mảng đầy đủ. Nửa bên trái của mảng, tôi chỉ cần đi tự ý quyết định rằng nửa trái sẽ nhỏ hơn so với nửa bên phải, bởi vì điều này sẽ xảy ra bao gồm ba yếu tố. 

Và do đó, tôi sẽ nói rằng nửa bên trái của một nửa trái mảng chỉ là những yếu tố năm. Năm, là một yếu tố duy nhất mảng, chúng tôi biết làm thế nào để sắp xếp nó. Và như vậy năm được sắp xếp. Chúng tôi chỉ muốn khai báo đó. Đó là một mảng yếu tố duy nhất. 

Vì vậy, bây giờ chúng tôi đã sắp xếp các nửa bên trái của half-- trái hay đúng hơn, chúng tôi đã sắp xếp các nửa bên trái của màu da cam. Vì vậy, bây giờ, để vẫn có đầy đủ nửa bên trái của mảng tổng thể, chúng ta cần phải sắp xếp một nửa bên phải của màu da cam, hoặc các công cụ này. Làm thế nào để chúng tôi làm điều đó? Vâng, chúng tôi có một mảng hai yếu tố. Vì vậy, chúng tôi có thể sắp xếp một nửa còn lại của các mảng, mà là hai. Hai là một yếu tố duy nhất. Vì vậy, nó được sắp xếp theo mặc định. Sau đó chúng tôi có thể sắp xếp một nửa bên phải phần đó của một dãy, một sự. Đó là loại mặc định. 

Điều này bây giờ là lần đầu tiên chúng tôi đã đạt đến một bước sáp nhập. Chúng tôi đã hoàn thành, mặc dù chúng tôi hiện loại lồng down-- và đó là sắp xếp của các khó khăn điều với đệ quy là, bạn cần để giữ cho bạn đi về nơi mà chúng ta đang có. Vì vậy, chúng tôi đã loại trái một nửa của phần cam. 

Và bây giờ, chúng ta đang ở giữa các phân loại nửa bên phải của phần cam. Và trong quá trình đó, chúng ta bây giờ về để được ở bước, hợp nhất hai nửa lại với nhau. Khi chúng ta nhìn vào hai nửa của mảng, chúng ta thấy hai và một. Yếu tố nào là nhỏ? One. 

Sau đó, yếu tố nào là nhỏ? Vâng, đó là hai hoặc không có gì. Vì vậy, nó là hai. Vì vậy, bây giờ, chỉ để lại khung nơi chúng tôi đang trong bối cảnh, chúng tôi đã sắp xếp các nửa bên trái của màu da cam và nửa bên phải của nguồn gốc. Tôi biết tôi đã thay đổi màu sắc một lần nữa, nhưng đó là nơi chúng tôi. Và lý do tôi đã làm điều này là bởi vì quá trình này là sẽ tiếp tục đi, lặp lại. Chúng tôi đã sắp xếp bên trái một nửa của màu da cam cũ và nửa bên phải của màu da cam cũ. 

Bây giờ, chúng ta cần phải hợp nhất những hai nửa lại với nhau quá. Đó là bước chúng ta đang ở trên. Vì vậy, chúng ta xem xét tất cả các yếu tố mà bây giờ là màu xanh lá cây, nửa bên trái của mảng ban đầu. Và chúng tôi kết hợp những bằng cách sử dụng quá trình tương tự chúng tôi đã làm cho việc sáp nhập hai và một trong những chỉ một thời gian trước đây. 

Nửa bên trái, nhỏ nhất yếu tố trên nửa bên trái là năm. Các phần tử nhỏ nhất trên nửa bên phải là một. Mà trong số đó là nhỏ hơn? One. 

Các phần tử nhỏ nhất trên nửa bên trái là năm. Các phần tử nhỏ nhất trên nửa bên phải là hai. Những gì là nhỏ nhất? Hai. Và rồi cuối cùng năm và không có gì, chúng ta có thể nói năm. 

OK, hình ảnh quá lớn, chúng ta hãy nghỉ ngơi cho một thứ hai và tìm ra nơi chúng ta đang có. Nếu chúng ta bắt đầu từ khi bắt đầu, chúng tôi Hiện tại đã hoàn thành mảng tổng chỉ một bước của mã giả ở đây. Chúng tôi đã sắp xếp các nửa bên trái của mảng. 

Nhớ lại rằng ban đầu Để lên năm, hai, một. Bằng cách đi qua quá trình này và làm tổ xuống và lặp đi lặp lại, tiếp tục phá vỡ các vấn đề thành nhiều phần nhỏ hơn và nhỏ hơn, bây giờ chúng tôi đã hoàn thành bước một trong những giả cho mảng bắt đầu toàn bộ. Chúng tôi đã sắp xếp một nửa bên trái của nó. 

Vì vậy, bây giờ hãy đóng băng ở đó. Và bây giờ hãy sắp xếp đúng các một nửa của mảng ban đầu. Và chúng ta sẽ làm điều đó bằng cách đi qua cùng lặp đi lặp lại quá trình phá vỡ những điều xuống và sau đó sáp nhập chúng lại với nhau. 

Vì vậy, nửa bên trái của màu đỏ, hoặc nửa trái của nửa bên phải của bản gốc mảng, tôi sẽ nói là ba. Một lần nữa, tôi là nhất quán ở đây. Nếu bạn có một kỳ lạ số yếu tố, nó không thực sự quan trọng cho dù bạn làm cho một trái nhỏ hơn hoặc phải một nhỏ hơn. 

Điều quan trọng là bất cứ khi nào bạn gặp phải vấn đề này trong việc thực hiện một hợp nhất, bạn cần phải phù hợp. Bạn có thể luôn luôn cần phải làm cho một bên trái nhỏ hơn hoặc luôn luôn cần phải thực hiện phía bên phải nhỏ hơn. Ở đây, tôi đã chọn luôn làm cho phía bên trái nhỏ hơn khi mảng của tôi, hoặc tôi sub-array, là một kích thước lẻ. 

Ba là một yếu tố duy nhất, và do đó, nó được sắp xếp. Chúng tôi đã thừa hưởng giả định rằng trong suốt toàn bộ quá trình của chúng tôi cho đến nay. Vì vậy, bây giờ hãy sắp xếp đúng các một nửa của nửa bên phải, hoặc nửa bên phải của màu đỏ. 

Một lần nữa, chúng ta cần phải phân chia này xuống. Đây không phải là một mảng yếu tố duy nhất. Chúng tôi không thể khai báo nó được sắp xếp. Và vì vậy đầu tiên, chúng ta sẽ để sắp xếp một nửa trái. 

Nửa bên trái là một yếu tố duy nhất, vì vậy nó loại theo mặc định. Sau đó chúng tôi sẽ sắp xếp quyền một nửa, đó là một yếu tố duy nhất. Nó được sắp xếp theo mặc định. Và bây giờ, chúng ta có thể kết hợp hai cùng nhau. Bốn là nhỏ hơn, và sau đó sáu là nhỏ hơn. 

Một lần nữa, những gì chúng tôi đã thực hiện tại thời điểm này? Chúng tôi đã sắp xếp bên trái một nửa của nửa bên phải. Hoặc sẽ trở lại với bản gốc màu sắc mà ở đó, chúng tôi đã sắp xếp bên trái một nửa màu đỏ nhẹ nhàng hơn. Ban đầu nó được một viên gạch tối màu đỏ và bây giờ nó là một màu đỏ nhẹ nhàng hơn, hoặc nó là một màu đỏ nhẹ nhàng hơn. 

Và sau đó chúng tôi đã sắp xếp các nửa bên phải của màu đỏ nhẹ nhàng hơn. Bây giờ, tốt, họ đang xanh một lần nữa, chỉ bởi vì chúng ta đang trải qua một quá trình. Và chúng ta phải lặp lại trên này và hơn. 

Vì vậy, bây giờ chúng tôi có thể kết hợp những hai nửa lại với nhau. Và đó là những gì chúng tôi làm ở đây. Vì vậy, các đường màu đen chỉ chia một nửa trái và nửa bên phải của phần loại này. 

Chúng tôi so sánh các giá trị nhỏ nhất ở phía bên trái của array-- hay tha thứ cho tôi, nhỏ nhất giá trị của một nửa trái với giá trị nhỏ nhất của quyền nửa và thấy rằng ba là nhỏ hơn. Và bây giờ là một chút của một tối ưu hóa, phải không? Có thực sự không có gì còn lại ở phía bên trái. 

Không có gì còn lại là ở bên trái, vì vậy chúng tôi có thể có hiệu quả chỉ move-- chúng ta có thể khai báo phần còn lại của nó là thực sự sắp xếp và chỉ tack nó trên, bởi vì không có gì khác để so sánh. Và chúng ta biết rằng phía bên phải của các bên phải được sắp xếp. 

OK, vì vậy bây giờ chúng ta hãy đóng băng một lần nữa và tìm ra nơi chúng ta đang ở trong câu chuyện. Trong mảng tổng thể, những gì chúng tôi đã thực hiện? Chúng tôi đã thực sự hoàn thành Bây giờ bước một và bước hai. Chúng tôi sắp xếp một nửa trái, và chúng tôi sắp xếp một nửa bên phải. 

Vì vậy, bây giờ, tất cả những gì còn lại là dành cho chúng tôi kết hợp hai nửa lại với nhau. Vì vậy, chúng ta so sánh các giá trị thấp nhất yếu tố của mỗi nửa của mảng lần lượt, và tham gia thảo luận. Một là ít hơn so với ba, vì vậy một trong những đi. 

Hai là ít hơn so với ba, vì vậy hai đi. Ba là ít hơn 5, do đó, ba đi. Bốn là ít hơn 5, do bốn đi. Sau đó năm là ít hơn sáu, và sáu là tất cả những gì còn lại. 

Bây giờ, tôi biết, đó là rất nhiều bước. Và chúng tôi đã để lại rất nhiều bộ nhớ trong thức của chúng tôi. Và đó là những gì những hình vuông màu xám. Và nó có thể cảm thấy như mất một nhiều thời gian hơn sắp xếp chèn, bong bóng sắp xếp, hoặc sắp xếp chọn. 

Nhưng thực sự, bởi vì một rất nhiều các quá trình đang xảy ra tại các time-- cùng đó là cái gì chúng ta sẽ thấy, một lần nữa, nói về khi chúng ta nói về đệ quy trong một tương lai video-- thuật toán này thực sự rõ ràng là cơ bản khác với bất cứ điều gì chúng ta đã thấy trước nhưng cũng là đáng kể hiệu quả hơn. 

Tại sao vậy? Vâng, trong tồi tệ nhất trường hợp kịch bản, chúng tôi có chia n yếu tố lên và sau đó kết hợp lại chúng. Nhưng khi chúng ta kết hợp lại chúng, những gì chúng tôi đang làm về cơ bản là tăng gấp đôi kích thước của mảng nhỏ hơn. Chúng tôi có một bó của một phần tử mảng mà chúng ta có hiệu quả kết hợp thành hai mảng phần tử. Và sau đó chúng ta lấy những hai mảng yếu tố và kết hợp chúng lại với nhau thành bốn mảng phần tử, và như vậy, và như vậy, và như vậy, cho đến khi chúng tôi có một mảng n phần tử duy nhất. 

Nhưng làm thế nào nhiều trùng lặp nó đi để có được để n? Hãy suy nghĩ lại với ví dụ danh bạ điện thoại. Đã bao nhiêu lần chúng ta phải xé danh bạ điện thoại trong một nửa, như thế nào nhiều hơn nữa lần làm chúng ta phải xé cuốn sách điện thoại một nửa, nếu kích thước của cuốn sách điện thoại tăng gấp đôi? Có chỉ là một, phải không? 

Vì vậy, có một số loại yếu tố logarit đây. Nhưng chúng ta cũng vẫn phải có ít nhất xem xét tất cả các yếu tố n. Vì vậy, trong trường hợp xấu nhất, hợp nhất phân loại chạy trong n log n. Chúng ta phải nhìn vào tất cả các yếu tố n, và chúng ta phải kết hợp chúng với nhau trong log n bộ các bước. Trong trường hợp tốt nhất, mảng được sắp xếp một cách hoàn hảo. Thật tuyệt. Nhưng dựa trên các thuật toán chúng ta có ở đây, chúng ta vẫn phải tách ra và tái kết hợp. Mặc dù trong trường hợp này, recombining là loại không có hiệu quả. Nó không phải là cần thiết. Nhưng chúng tôi vẫn đi qua toàn bộ quá trình anyway. 

Vì vậy, trong trường hợp tốt nhất và trong trường hợp xấu nhất, thuật toán này chạy trong n log n lần. Hợp nhất phân loại chắc chắn là một chút phức tạp hơn hơn so với các thuật toán phân loại chính khác chúng tôi đã nói chuyện về CS50 nhưng là đáng kể mạnh hơn. 

Và do đó, nếu bạn đã bao giờ tìm thấy Nhân dịp cần đến nó hoặc sử dụng nó để sắp xếp một tập hợp dữ liệu lớn, nhận được đầu của bạn xung quanh ý tưởng của đệ quy là có được thực sự mạnh mẽ. Và nó sẽ làm cho bạn chương trình thực sự hiệu quả hơn sử dụng hợp nhất phân loại so với bất cứ điều gì khác. Tôi Doug Lloyd. Đây là CS50.