[เล่นเพลง] 

DOUG LLOYD: ตกลงดังนั้นผสาน การจัดเรียงเป็นอีกขั้นตอนวิธีการอื่น ที่เราสามารถใช้การจัดเรียงออก องค์ประกอบของอาร์เรย์ แต่ที่เราจะเห็นก็มี ความแตกต่างพื้นฐานมาก จากการเรียงลำดับการเลือกฟอง เรียงลำดับและการจัดเรียงแทรก ที่ทำให้มันสวยจริงๆฉลาด 

ความคิดพื้นฐานหลังผสาน การเรียงลำดับการจัดเรียงเป็นอาร์เรย์ที่มีขนาดเล็ก แล้วรวมอาร์เรย์เหล่านั้น ร่วมกันหรือรวม them-- จึง name-- เพื่อเรียงลำดับ วิธีการที่ผสานการเรียงลำดับไม่ นี้โดยใช้ประโยชน์จากเครื่องมือ ที่เรียกว่าการเรียกซ้ำซึ่งเป็นสิ่งที่ ที่เรากำลังจะพูดคุยเกี่ยวกับในเร็ว ๆ นี้ แต่เรายังไม่ได้คุยมากเกี่ยวกับยัง 

นี่คือความคิดพื้นฐานที่อยู่เบื้องหลังการจัดเรียงผสาน เรียงครึ่งซ้ายของอาร์เรย์ สมมติว่า n มากกว่า 1 และสิ่งที่ผมหมายถึงเมื่อฉันพูด สมมติว่า n มากกว่า 1 คือ ผมคิดว่าเราสามารถตกลงว่าถ้าอาร์เรย์ เพียงประกอบด้วยองค์ประกอบเดียว มันเรียง เราไม่จำเป็นต้องจริง ที่จะทำอะไรกับมัน เราก็สามารถประกาศให้มีการเรียง มันเป็นเพียงองค์ประกอบหนึ่ง 

ดังนั้น pseudocode อีกครั้งเป็น เรียงลำดับครึ่งด้านซ้ายของอาร์เรย์ แล้วเรียงครึ่งขวาอาร์เรย์ แล้วรวมทั้งสองส่วนเข้าด้วยกัน ตอนนี้แล้วคุณอาจจะ คิดชนิดของมันเพียง เสียงเหมือนคุณกำลังวางปิด the-- คุณไม่ได้จริงทำอะไร คุณกำลังจะบอกว่าการจัดเรียงซ้าย ครึ่งเรียงลำดับครึ่งขวา แต่คุณไม่ได้บอก ฉันว่าคุณกำลังทำมัน 

แต่จำไว้ว่าตราบใดที่ อาร์เรย์เป็นองค์ประกอบเดียว เราสามารถประกาศเรียง จากนั้นเราก็สามารถรวมเข้าด้วยกัน และที่จริง ความคิดพื้นฐานที่อยู่เบื้องหลังการจัดเรียงผสาน คือการทำลายมันลงเพื่อให้ อาร์เรย์ของคุณมีขนาดหนึ่ง และจากนั้นคุณสร้างจากที่นั่น 

ผสานการเรียงลำดับแน่นอน อัลกอริทึมที่มีความซับซ้อน และก็ยังเล็ก ๆ น้อย ๆ ที่มีความซับซ้อนที่จะเห็นภาพ ดังนั้นหวังว่าการสร้างภาพว่าเราคือ มีที่นี่จะช่วยให้คุณทำตาม และผมจะพยายามทำให้ดีที่สุดที่จะเล่าสิ่งที่ และดำเนินการผ่านเล็ก ๆ น้อย ๆ นี้ ช้ากว่าคนอื่น ๆ เพียงเพื่อหวังว่าจะได้รับหัวของคุณ ความคิดที่อยู่เบื้องหลังรอบจัดเรียงผสาน 

ดังนั้นเราจึงมีอาร์เรย์เช่นเดียวกับ วิดีโอขั้นตอนวิธีการเรียงลำดับอื่น ๆ ถ้าคุณเคยเห็น them-- อาร์เรย์องค์ประกอบหก และรหัส pseudocode ของเราที่นี่คือการจัดเรียง ครึ่งซ้ายจัดเรียงครึ่งขวา รวมทั้งสองส่วนเข้าด้วยกัน ดังนั้นลองมาสีแดงอิฐสีเข้มมากนี้ อาร์เรย์และเรียงลำดับครึ่งซ้ายของมัน 

ดังนั้นในขณะนี้เรากำลังจะ ที่จะไม่สนใจสิ่งที่อยู่บนด้านขวา ก็มี แต่เรา ไม่ได้อยู่ที่ขั้นตอนที่ยัง เราไม่ได้อยู่ที่การจัดเรียง ครึ่งขวาของอาร์เรย์ เราที่จัดเรียงซ้าย ครึ่งหนึ่งของอาร์เรย์ และเพียงเพื่อประโยชน์ ของการเป็นเล็ก ๆ น้อย ๆ ที่ชัดเจนเพื่อให้สามารถดู กับสิ่งที่ขั้นตอนที่เราอยู่ ฉันจะเปลี่ยน สีของชุดนี้เป็นสีส้ม ตอนนี้เราก็ยังคงพูดคุยเกี่ยวกับ ครึ่งซ้ายเดียวกันของอาร์เรย์เดิม แต่ฉันหวังว่าด้วยความสามารถในการ หมายถึงสีของรายการต่างๆ มันจะทำให้มันเล็ก ๆ น้อย ๆ ที่ชัดเจนสิ่งที่เกิดขึ้นที่นี่ 

ตกลงดังนั้นตอนนี้เรามี สามองค์ประกอบอาร์เรย์ ทำอย่างไรเราจะเรียงลำดับในช่วงครึ่งปีที่เหลือนี้ อาร์เรย์ซึ่งยังคงเป็นขั้นตอนนี้? เรากำลังพยายามที่จะเรียงลำดับซ้าย ครึ่งหนึ่งของสีแดงอิฐ array-- ครึ่งซึ่งทางด้านซ้ายของ ฉันได้สีส้มในขณะนี้ 

ดีเราอาจจะลองและ ทำซ้ำขั้นตอนนี้อีกครั้ง ดังนั้นเรายังคงอยู่ใน ตรงกลางของความพยายามในการจัดเรียง ครึ่งซ้ายของมากมายเต็ม ครึ่งซ้ายของ อาร์เรย์ฉันแค่ไป ไปโดยพลการตัดสินใจว่าครึ่งซ้าย จะมีขนาดเล็กกว่าครึ่งหนึ่งที่เหมาะสม เพราะนี้เกิดขึ้นกับ ประกอบด้วยสามองค์ประกอบ 

และเพื่อที่ฉันจะบอกว่า ครึ่งซ้ายของครึ่งซ้ายอาร์เรย์ เป็นเพียงองค์ประกอบห้า ห้าเป็นองค์ประกอบหนึ่ง อาร์เรย์เรารู้วิธีการจัดเรียง และเพื่อให้ห้าเรียง เรากำลังจะประกาศว่า มันเป็นองค์ประกอบหนึ่งอาร์เรย์ 

ดังนั้นเราจึงได้เรียงตอนนี้ ครึ่งซ้ายของ half-- ซ้าย หรือมากกว่าที่เราเคยเรียง ครึ่งซ้ายของสีส้ม ดังนั้นตอนนี้เพื่อที่จะยังคงสมบูรณ์ ครึ่งซ้ายอาร์เรย์โดยรวมของ เราจำเป็นต้องเรียงลำดับครึ่งหนึ่งที่เหมาะสม สีส้มหรือสิ่งนี้ เราจะทำอย่างนั้นได้อย่างไร? ดีที่เรามีอาร์เรย์องค์ประกอบที่สอง ดังนั้นเราจึงสามารถจัดเรียงครึ่งซ้าย ของอาเรย์ซึ่งเป็นสอง สองเป็นองค์ประกอบเดียว ดังนั้นจึงเรียงตามค่าเริ่มต้น จากนั้นเราก็สามารถจัดเรียงครึ่งหนึ่งที่เหมาะสม จากส่วนของอาร์เรย์ที่หนึ่ง นั่นคือการจัดเรียงของโดยค่าเริ่มต้น 

นี่คือตอนนี้เป็นครั้งแรก เราได้มาถึงขั้นตอนการผสาน เราได้เสร็จสิ้นแม้ว่า เรากำลังซ้อนกันในขณะนี้ชนิดของ down-- และนั่นคือการจัดเรียงของหากิน สิ่งที่มีการเรียกซ้ำคือ คุณจะต้องให้คุณ หัวเกี่ยวกับการที่เรามี ดังนั้นเราจึงได้จัดเรียงของด้านซ้าย ครึ่งหนึ่งของส่วนสีส้ม 

และตอนนี้เรากำลังอยู่ในช่วงกลางของการเรียงลำดับ ครึ่งขวาของส่วนสีส้ม และในกระบวนการที่เรามี ขณะนี้เกี่ยวกับที่จะอยู่ในขั้นตอน รวมทั้งสองส่วนเข้าด้วยกัน เมื่อเรามองที่ทั้งสองส่วน ของอาร์เรย์ที่เราเห็นสองและเป็นหนึ่งใน ซึ่งองค์ประกอบที่มีขนาดเล็ก? หนึ่ง 

จากนั้นองค์ประกอบที่มีขนาดเล็ก? ดีก็สองหรืออะไร ดังนั้นจึงเป็นที่สอง ดังนั้นตอนนี้เพียงเพื่อให้กรอบอีกครั้ง ที่เรามีในบริบท เราได้เรียง ครึ่งซ้ายของสีส้ม และอีกครึ่งหนึ่งที่เหมาะสมของแหล่งกำเนิด ฉันรู้ว่าฉันได้เปลี่ยนสี อีกครั้ง แต่นั่นคือสิ่งที่เราเป็น และเหตุผลที่ฉันทำอย่างนี้ เป็นเพราะกระบวนการนี​​้คือ จะให้ไปทำซ้ำลง เราได้เรียงซ้าย ครึ่งหนึ่งของส้มอดีต และอีกครึ่งหนึ่งขวาของส้มอดีต 

ตอนนี้เราต้องการที่จะรวมเหล่านั้น สองส่วนด้วยกันเกินไป นั่นเป็นขั้นตอนที่เราอยู่บน ดังนั้นเราจึงพิจารณาทั้งหมดของ องค์ประกอบที่มีตอนนี้สีเขียว ครึ่งซ้ายของแถวเดิม และเรารวมเหล่านั้น โดยใช้กระบวนการเดียวกัน เราไม่ได้สำหรับการรวมสอง และเป็นหนึ่งในเพียงครู่ที่ผ่านมา 

ครึ่งซ้ายที่เล็กที่สุด องค์ประกอบครึ่งซ้ายเป็นห้า องค์ประกอบที่เล็กที่สุดใน ครึ่งขวาเป็นหนึ่ง ซึ่งในนั้นคือเล็ก? หนึ่ง 

องค์ประกอบที่เล็กที่สุดใน ครึ่งซ้ายเป็นห้า องค์ประกอบที่เล็กที่สุดใน ครึ่งขวาสอง ที่เล็กที่สุดคืออะไร? สอง และแล้วในที่สุดห้า ไม่มีอะไรที่เราสามารถพูดได้ห้า 

ตกลงภาพใหญ่เพื่อขอ ใช้เวลาพักเป็นครั้งที่สอง และคิดออกว่าเราอยู่ที่ไหน ถ้าเราเริ่มต้นจาก จุดเริ่มต้นมากเรา ได้เสร็จสิ้นในขณะนี้สำหรับ อาร์เรย์โดยรวมเพียง หนึ่งในขั้นตอนของรหัส pseudocode ที่นี่ เราได้เรียง ครึ่งซ้ายของอาร์เรย์ 

จำได้ว่าเดิม เพื่อเป็นห้าสองหนึ่ง โดยจะผ่านขั้นตอนนี้ และทำรังลงและทำซ้ำ อย่างต่อเนื่องที่จะทำลายปัญหา ลงไปในชิ้นส่วนที่มีขนาดเล็กและขนาดเล็ก เราได้เสร็จสิ้นในขณะนี้ ขั้นตอนที่หนึ่ง pseudocode สำหรับอาร์เรย์เริ่มต้นทั้งหมด เราได้เรียงครึ่งซ้าย 

ดังนั้นตอนนี้เรามีการแช่แข็ง และตอนนี้เรามาเรียงลำดับที่ถูกต้อง ครึ่งหนึ่งของอาร์เรย์เดิม และเรากำลังจะทำด้วย จะผ่านเดียวกันซ้ำแล้วซ้ำอีก กระบวนการของการทำลายสิ่งที่ลง และจากนั้นการรวมเข้าด้วยกัน 

ดังนั้นในช่วงครึ่งซ้ายของ สีแดงหรือครึ่งซ้าย ในช่วงครึ่งขวาของเดิม อาร์เรย์ฉันจะบอกก็คือสาม อีกครั้งฉันมีความสอดคล้องกันที่นี่ หากคุณมีความแปลก จำนวนขององค์ประกอบมัน ไม่ได้เรื่องจริงๆไม่ว่าจะเป็น คุณทำให้คนที่เหลือที่มีขนาดเล็ก หรือขวาหนึ่งที่มีขนาดเล็ก 

สิ่งที่สำคัญคือว่าเมื่อใดก็ตามที่คุณ พบปัญหานี้ในการดำเนินการ ผสานคุณจะต้องมีความสอดคล้อง คุณอาจจำเป็นต้อง ทำให้ด้านซ้ายที่มีขนาดเล็ก หรือมักจะต้องทำให้ ด้านขวาที่มีขนาดเล็ก ที่นี่ผมได้เลือกที่จะเสมอ ทำให้ด้านซ้ายที่มีขนาดเล็ก เมื่ออาเรย์ของฉันหรือของฉัน อาร์เรย์ย่อยคือมีขนาดที่แปลก 

สามเป็นองค์ประกอบเดียว และดังนั้นจึงจะถูกจัดเรียง เราได้ยกระดับสมมติฐานที่ว่า ตลอดกระบวนการทั้งหมดของเราเพื่อให้ห่างไกล ดังนั้นตอนนี้เรามาเรียงลำดับที่ถูกต้อง ครึ่งหนึ่งของครึ่งขวา หรือครึ่งขวาของสีแดง 

อีกครั้งที่เราต้องแบ่งนี้ลง นี้ไม่ได้เป็นอาร์เรย์องค์ประกอบหนึ่ง เราไม่สามารถประกาศเรียง และเป็นครั้งแรกดังนั้นเราจะ การจัดเรียงครึ่งซ้าย 

ครึ่งซ้ายเป็นองค์ประกอบเดียว ดังนั้นจึงเป็นเรื่องของการจัดเรียงโดยค่าเริ่มต้น จากนั้นเราจะเรียงลำดับที่ถูกต้อง ครึ่งซึ่งเป็นองค์ประกอบหนึ่ง มันเรียงตามค่าเริ่มต้น และตอนนี้, เราสามารถผสานทั้งสองเข้าด้วยกัน สี่มีขนาดเล็กและ จากนั้นหกมีขนาดเล็ก 

อีกครั้งสิ่งที่เราทำในตอนนี้? เราได้เรียงซ้าย ครึ่งหนึ่งของครึ่งที่เหมาะสม หรือจะกลับไปที่เดิม สีที่อยู่ที่นั่น เราได้เรียงซ้าย ครึ่งหนึ่งของสีแดงนุ่ม แต่เดิมมันเป็นอิฐที่มืด สีแดงและตอนนี้ก็เป็นสีแดงอ่อน หรือมันเป็นสีแดงนุ่ม 

และจากนั้นเราได้เรียง ครึ่งขวาของสีแดงนุ่ม ตอนนี้ดีที่พวกเขากำลังสีเขียวอีกครั้งเพียง เพราะเรากำลังจะผ่านกระบวนการ และเราจะต้องทำซ้ำ นี้ซ้ำแล้วซ้ำอีก 

ดังนั้นตอนนี้เราสามารถผสานเหล่านั้น ทั้งสองส่วนเข้าด้วยกัน และนั่นคือสิ่งที่เราทำที่นี่ ดังนั้นเส้นสีดำเพียง แบ่งครึ่งซ้าย และอีกครึ่งหนึ่งทางด้านขวาของส่วนการจัดเรียงนี้ 

เราเปรียบเทียบค่าที่น้อยที่สุด ที่ด้านซ้ายของ array-- หรือขอโทษนะที่มีขนาดเล็กที่สุด ค่าของครึ่งซ้าย ค่าที่เล็กที่สุดของที่เหมาะสม ช่วงครึ่งปีและพบว่าทั้งสามมีขนาดเล็ก และตอนนี้บิตของการเพิ่มประสิทธิภาพใช่มั้ย? ไม่มีอะไรที่เป็นจริง ที่เหลืออยู่บนด้านซ้าย 

ไม่มีอะไรที่เหลืออยู่คือ ที่ด้านข้างซ้าย เพื่อให้เราสามารถได้อย่างมีประสิทธิภาพ เพียง move-- เราสามารถประกาศ ส่วนที่เหลือของมันเป็นจริง เรียงตะปูและเพียงแค่มัน บนเพราะไม่มีอะไร อื่นที่จะเปรียบเทียบกับ และเรารู้ว่าด้านขวา ของทางด้านขวาจะถูกจัดเรียง 

ตกลงดังนั้นตอนนี้ขอหยุดอีกครั้งและ คิดออกว่าเราอยู่ในเรื่อง ในอาร์เรย์โดยรวม สิ่งที่เราประสบความสำเร็จ? เราได้ประสบความสำเร็จจริง ขณะนี้ขั้นตอนที่หนึ่งและสองขั้นตอน เราเรียงครึ่งซ้ายและ เราเรียงครึ่งหนึ่งที่เหมาะสม 

ดังนั้นตอนนี้ทุกคนที่ยังคงเป็นสำหรับเรา ที่จะรวมทั้งสองส่วนเข้าด้วยกัน ดังนั้นเราจึงเปรียบเทียบมูลค่าต่ำสุด องค์ประกอบของแต่ละครึ่งของอาร์เรย์ ในการเปิดและดำเนินการต่อ หนึ่งคือน้อยกว่าสามดังนั้นหนึ่งไป 

สองคือน้อยกว่าสามเพื่อให้ทั้งสองไป สามคือน้อยกว่า 5 ดังนั้นสามไป สี่คือน้อยกว่า 5 ดังนั้นสี่ไป จากนั้นห้าน้อยกว่าหก และหกเป็นสิ่งที่ยังคงอยู่ 

ตอนนี้ฉันรู้ว่าเป็นจำนวนมากของขั้นตอน และเราได้ทิ้งเป็นจำนวนมาก ของหน่วยความจำในการปลุกของเรา และนั่นคือสิ่งสี่เหลี่ยมสีเทาผู้ที่มี และมันอาจจะรู้สึกเหมือนที่เอา มากเกินกว่าการจัดเรียงแทรกฟอง เรียงลำดับหรือการเรียงลำดับการเลือก 

แต่จริงๆแล้วเพราะ จำนวนมากของกระบวนการเหล่านี้ จะเกิดขึ้นที่ time-- เดียวกัน ซึ่งเป็นสิ่งที่เราจะอีกครั้ง พูดคุยเกี่ยวกับเมื่อเราพูดคุยเกี่ยวกับ เรียกซ้ำในอนาคต video-- ขั้นตอนวิธีนี้จริง เห็นได้ชัดว่าเป็นพื้นฐาน ที่แตกต่างกันกว่าสิ่งใด เราได้เห็นมาก่อน แต่ก็ยังเป็นอย่างมีนัยสำคัญ มีประสิทธิภาพมากขึ้น 

ว่าเป็นเพราะเหตุใด ทั้งในที่เลวร้ายที่สุด กรณีที่เรามี การแยกองค์ประกอบ n ขึ้น และจากนั้นพวกเขา recombine แต่เมื่อเรา recombine พวกเขาสิ่งที่เรากำลังทำ เป็นพื้นสองเท่า ขนาดของอาร์เรย์ที่มีขนาดเล็ก เรามีพวงของหนึ่งในองค์ประกอบ อาร์เรย์ที่เราได้อย่างมีประสิทธิภาพ รวมเป็นสองอาร์เรย์องค์ประกอบ และจากนั้นเราใช้เวลาเหล่านั้น สองอาร์เรย์องค์ประกอบ และรวมเข้าด้วยกันเป็น สี่อาร์เรย์องค์ประกอบและอื่น ๆ และอื่น ๆ และอื่น ๆ จนเรา มีอาร์เรย์องค์ประกอบ n เดียว 

แต่กี่ doublings มันจะใช้เวลาที่จะได้รับ n? คิดว่ากลับไปเช่นสมุดโทรศัพท์ กี่ครั้งแล้วที่เราจะต้องฉีก สมุดโทรศัพท์ในช่วงครึ่งปีวิธีการอื่น ๆ อีกมากมาย ครั้งเราจะต้องฉีกสมุดโทรศัพท์ ในช่วงครึ่งปีถ้าขนาดของสมุดโทรศัพท์ สองเท่า? มีเพียงหนึ่งเป็นใช่มั้ย? 

ดังนั้นจึงมีการจัดเรียงของบางอย่าง องค์ประกอบลอการิทึมที่นี่ แต่เราก็ยังคงมีอย่างน้อย ดูทุกองค์ประกอบที่ n ดังนั้นในสถานการณ์กรณีที่เลวร้ายที่สุด ผสานการจัดเรียงทำงานใน n ล็อก n เราต้องมองไปที่ ทุกองค์ประกอบ n ที่ และเราจะต้องรวมพวกเขา ร่วมกันในชุด n เข้าสู่ระบบของขั้นตอน ในกรณีที่ดีที่สุด อาร์เรย์จะถูกจัดเรียงอย่างสมบูรณ์แบบ นั่นวิเศษมาก แต่ขึ้นอยู่กับขั้นตอนวิธีการที่เรามีที่นี่ เรายังคงต้องแยกและ recombine ถึงแม้ว่าในกรณีนี้ recombining เป็นชนิดของการไม่ได้ผล มันไม่จำเป็นต้อง แต่เรายังคงผ่านไป กระบวนการทั้งหมดอยู่แล้ว 

ดังนั้นในกรณีที่ดีที่สุด และในกรณีที่เลวร้ายที่สุด ขั้นตอนวิธีการนี​​้จะทำงานในบันทึก n n เวลา ผสานการเรียงลำดับแน่นอนบิต trickier กว่าขั้นตอนวิธีการเรียงลำดับหลักอื่น ๆ เราได้พูดคุยเกี่ยวกับ CS50 แต่ อย่างมีนัยสำคัญมีประสิทธิภาพมากขึ้น 

ดังนั้นถ้าคุณเคยพบ โอกาสที่จะจำเป็นต้องใช้มัน หรือเพื่อใช้ในการเรียงลำดับ ชุดข้อมูลขนาดใหญ่ที่ได้รับ หัวของรอบความคิดของการเรียกซ้ำตัวเอง เป็นไปได้ที่มีประสิทธิภาพจริงๆ และมันจะทำให้คุณ โปรแกรมมากจริงๆมีประสิทธิภาพมากขึ้น โดยใช้การผสานการเรียงลำดับเมื่อเทียบกับสิ่งอื่น ฉันลอยด์ดั๊ก นี่คือ CS50