{"id":12215,"date":"2020-08-05T09:00:00","date_gmt":"2020-08-05T07:00:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=12215"},"modified":"2025-12-04T12:05:19","modified_gmt":"2025-12-04T11:05:19","slug":"mergesort","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/mergesort\/","title":{"rendered":"Mergesort \u2013 Algorithmus, Quellcode, Zeitkomplexit\u00e4t"},"content":{"rendered":"\n<p>In diesem Artikel <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>lernst Du, wie Mergesort (oft auch \"Merge Sort\") funktioniert,<\/li>\n\n\n\n<li>findest Du den Quellcode von Mergesort<\/li>\n\n\n\n<li>und du erf\u00e4hrst, wie man die Zeitkomplexit\u00e4t von Mergesort bestimmt, und zwar ohne komplizierte Mathematik.<\/li>\n<\/ul>\n\n\n\n<p>Dies ist nach <a href=\"\/de\/algorithmen\/quicksort\/\">Quicksort<\/a> der zweite effiziente Sortieralgorithmus aus der&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/sortieralgorithmen\/\">Artikelserie \u00fcber Sortieralgorithmen<\/a>.<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe title=\"Mergesort Algorithmus [mit Animation, Deutsch]\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/Ch49YYjkNv8?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"mergesort-algorithmus\">Mergesort Algorithmus<\/h2>\n\n\n\n<p>Mergesort funktioniert nach dem \u201eTeile-und-herrsche\u201c-Prinzip (\u201edivide and conquer\u201c):<\/p>\n\n\n\n<p>Zun\u00e4chst werden die zu sortierenden Elemente in zwei H\u00e4lften geteilt. Die entstandenen Sub-Arrays werden dann wieder geteilt \u2013 und wieder, bis Sub-Arrays der L\u00e4nge 1 entstanden sind:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1178\" height=\"658\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_divide-v2.png\" alt=\"Mergesort Algorithmus - Teilen\" class=\"wp-image-15129\" style=\"width:589px;height:329px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_divide-v2.png 1178w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_divide-v2-224x125.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_divide-v2-336x188.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_divide-v2-504x282.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_divide-v2-672x375.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_divide-v2-400x223.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_divide-v2-600x335.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_divide-v2-800x447.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_divide-v2-944x527.png 944w\" sizes=\"(max-width: 1178px) 100vw, 1178px\" \/><\/figure>\n<\/div>\n\n\n<p>Nun werden in umgekehrter Richtung jeweils zwei Teil-Arrays so zusammengef\u00fchrt (\"gemerged\"), dass jeweils ein sortiertes Array entsteht. Im letzten Schritt werden die zwei H\u00e4lften des urspr\u00fcnglichen Arrays gemerged, so dass dieses letztendlich sortiert ist.<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1270\" height=\"660\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge-v2.png\" alt=\"Mergesort Algorithmus - Mergen\" class=\"wp-image-15131\" style=\"width:635px;height:330px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge-v2.png 1270w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge-v2-224x116.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge-v2-336x175.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge-v2-504x262.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge-v2-672x349.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge-v2-400x208.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge-v2-600x312.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge-v2-800x416.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge-v2-944x491.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge-v2-1200x624.png 1200w\" sizes=\"(max-width: 1270px) 100vw, 1270px\" \/><\/figure>\n<\/div>\n\n\n<p>Wie genau zwei Teil-Arrays zu einem gemerged werden, wirst du in folgendem Beispiel sehen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"mergesort-merge-beispiel\">Mergesort Merge Beispiel<\/h3>\n\n\n\n<p>Das Mergen an sich funktioniert ganz einfach: F\u00fcr beide Arrays wird ein Merge-Index festgelegt, der zun\u00e4chst auf das erste Element des jeweiligen Arrays zeigt. Am einfachsten l\u00e4sst sich das an einem Beispiel zeigen (die Pfeile stellen den jeweiligen Merge-Index dar):<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1248\" height=\"564\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step1-v2.png\" alt=\"Mergesort Algorithmus - Merge-Beispiel - Schritt 1\" class=\"wp-image-15118\" style=\"width:624px;height:282px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step1-v2.png 1248w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step1-v2-224x101.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step1-v2-336x152.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step1-v2-504x228.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step1-v2-672x304.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step1-v2-400x181.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step1-v2-600x271.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step1-v2-800x362.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step1-v2-944x427.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step1-v2-1200x542.png 1200w\" sizes=\"(max-width: 1248px) 100vw, 1248px\" \/><\/figure>\n<\/div>\n\n\n<p>Die Elemente, auf die die Merge-Zeiger zeigen, werden verglichen. Das kleinere von beiden (im Beispiel die 1) wird an ein neues Arrays angeh\u00e4ngt und der Zeiger, der auf dieses Element gezeigt hat, wird um ein Feld nach rechts verschoben:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1248\" height=\"564\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step2-v3-1.png\" alt=\"Mergesort Algorithmus - Merge-Beispiel - Schritt 2\" class=\"wp-image-15145\" style=\"width:624px;height:282px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step2-v3-1.png 1248w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step2-v3-1-224x101.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step2-v3-1-336x152.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step2-v3-1-504x228.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step2-v3-1-672x304.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step2-v3-1-400x181.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step2-v3-1-600x271.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step2-v3-1-800x362.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step2-v3-1-944x427.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step2-v3-1-1200x542.png 1200w\" sizes=\"(max-width: 1248px) 100vw, 1248px\" \/><\/figure>\n<\/div>\n\n\n<p>Jetzt werden erneut die Elemente \u00fcber den Zeigern verglichen. Dieses mal ist die 2 kleiner als die 4, somit wird die 2 an das neue Array angeh\u00e4ngt:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1248\" height=\"564\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step3-v2.png\" alt=\"Mergesort Algorithmus - Merge-Beispiel - Schritt 3\" class=\"wp-image-15137\" style=\"width:624px;height:282px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step3-v2.png 1248w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step3-v2-224x101.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step3-v2-336x152.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step3-v2-504x228.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step3-v2-672x304.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step3-v2-400x181.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step3-v2-600x271.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step3-v2-800x362.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step3-v2-944x427.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step3-v2-1200x542.png 1200w\" sizes=\"(max-width: 1248px) 100vw, 1248px\" \/><\/figure>\n<\/div>\n\n\n<p>Jetzt liegen die Zeiger auf der 3 und der 4. Die 3 ist kleiner und wird an das Ziel-Array angeh\u00e4ngt:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1248\" height=\"564\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step4-v2.png\" alt=\"Mergesort Algorithmus - Merge-Beispiel - Schritt 4\" class=\"wp-image-15139\" style=\"width:624px;height:282px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step4-v2.png 1248w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step4-v2-224x101.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step4-v2-336x152.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step4-v2-504x228.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step4-v2-672x304.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step4-v2-400x181.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step4-v2-600x271.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step4-v2-800x362.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step4-v2-944x427.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step4-v2-1200x542.png 1200w\" sizes=\"(max-width: 1248px) 100vw, 1248px\" \/><\/figure>\n<\/div>\n\n\n<p>Jetzt ist die 4 am kleinsten:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1248\" height=\"564\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step5-v2.png\" alt=\"Mergesort Algorithmus - Merge-Beispiel - Schritt 5\" class=\"wp-image-15140\" style=\"width:624px;height:282px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step5-v2.png 1248w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step5-v2-224x101.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step5-v2-336x152.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step5-v2-504x228.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step5-v2-672x304.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step5-v2-400x181.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step5-v2-600x271.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step5-v2-800x362.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step5-v2-944x427.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step5-v2-1200x542.png 1200w\" sizes=\"(max-width: 1248px) 100vw, 1248px\" \/><\/figure>\n<\/div>\n\n\n<p>Jetzt die 5:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1248\" height=\"564\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step6-v2.png\" alt=\"Mergesort Algorithmus - Merge-Beispiel - Schritt 6\" class=\"wp-image-15142\" style=\"width:624px;height:282px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step6-v2.png 1248w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step6-v2-224x101.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step6-v2-336x152.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step6-v2-504x228.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step6-v2-672x304.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step6-v2-400x181.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step6-v2-600x271.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step6-v2-800x362.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step6-v2-944x427.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step6-v2-1200x542.png 1200w\" sizes=\"(max-width: 1248px) 100vw, 1248px\" \/><\/figure>\n<\/div>\n\n\n<p>Und im letzten Schritt bleibt die 6 \u00fcbrig und wird an das neue Array angeh\u00e4ngt:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1248\" height=\"604\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step7-v2.png\" alt=\"Mergesort Algorithmus - Merge-Beispiel - Schritt 7\" class=\"wp-image-15143\" style=\"width:624px;height:302px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step7-v2.png 1248w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step7-v2-224x108.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step7-v2-336x163.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step7-v2-504x244.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step7-v2-672x325.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step7-v2-400x194.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step7-v2-600x290.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step7-v2-800x387.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step7-v2-944x457.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_algorithm_merge_example_step7-v2-1200x581.png 1200w\" sizes=\"(max-width: 1248px) 100vw, 1248px\" \/><\/figure>\n<\/div>\n\n\n<p>Die zwei sortierten Teil-Arrays wurden durch das Mergen zu einem sortierten Gesamt-Array.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"mergesort-beispiel\">Mergesort Beispiel<\/h3>\n\n\n\n<p>Hier noch mal ein Beispiel f\u00fcr den Gesamt-Algorithmus. Sortiert werden soll das aus den anderen Teilen der Serie bekannte Array [3, 7, 1, 8, 2, 5, 9, 4, 6].<\/p>\n\n\n<div class=\"convertkit-form wp-block-convertkit-form\" style=\"\"><script async data-uid=\"5c918c0177\" src=\"https:\/\/happycoders.kit.com\/5c918c0177\/index.js\" data-jetpack-boost=\"ignore\" data-no-defer=\"1\" data-no-optimize=\"1\" nowprocket><\/script><\/div>\n\n\n\n<p>Dieses wird zun\u00e4chst solange geteilt, bis Arrays der L\u00e4nge 1 entstehen. Die Anordnung der Elemente \u00e4ndert sich dabei nicht:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"890\" height=\"930\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_divide.png\" alt=\"Mergesort Beispiel: Divide\" class=\"wp-image-15158\" style=\"width:445px;height:465px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_divide.png 890w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_divide-224x234.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_divide-336x351.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_divide-504x527.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_divide-672x702.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_divide-400x418.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_divide-600x627.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_divide-800x836.png 800w\" sizes=\"(max-width: 890px) 100vw, 890px\" \/><\/figure>\n<\/div>\n\n\n<p>Jetzt werden die Teil-Arrays in umgekehrter Richtung nach dem oben beschriebenen Prinzip gemerged. Im ersten Schritt werden die 4 und die 6 zum Teil-Array [4, 6] zusammengefasst:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"982\" height=\"410\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step1.png\" alt=\"Mergesort Beispiel: Merge Schritt 1\" class=\"wp-image-15157\" style=\"width:491px;height:205px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step1.png 982w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step1-224x94.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step1-336x140.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step1-504x210.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step1-672x281.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step1-400x167.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step1-600x251.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step1-800x334.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step1-944x394.png 944w\" sizes=\"(max-width: 982px) 100vw, 982px\" \/><\/figure>\n<\/div>\n\n\n<p>Als n\u00e4chstes werden die 3 und die 7 zum Teil-Array [3, 7] gemerged, 1 und 8 zum Teil-Array [1, 8], die 2 und die 5 werden zu [2, 5]. Bis hierhin standen die gemergeten Elemente zuf\u00e4llig in der richtigen Reihenfolge zueinander und wurden daher nicht verschoben.<\/p>\n\n\n\n<p>Das \u00e4ndert sich jetzt: Die 9 wird mit dem Teil-Array [4, 6] gemerged \u2013 dabei wandert die 9 ans Ende des neuen Teil-Arrays [4, 6, 9]:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"982\" height=\"410\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step2.png\" alt=\"Mergesort Beispiel: Merge Schritt 2\" class=\"wp-image-15159\" style=\"width:491px;height:205px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step2.png 982w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step2-224x94.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step2-336x140.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step2-504x210.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step2-672x281.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step2-400x167.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step2-600x251.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step2-800x334.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step2-944x394.png 944w\" sizes=\"(max-width: 982px) 100vw, 982px\" \/><\/figure>\n<\/div>\n\n\n<p>[3, 7] und [1, 8] werden nun zu [1, 3, 7, 8] gemerged. [2, 5] und [4, 6, 9] werden zu [2, 4, 5, 6, 9]:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"982\" height=\"410\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step3.png\" alt=\"Mergesort Beispiel: Merge Schritt 3\" class=\"wp-image-15161\" style=\"width:491px;height:205px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step3.png 982w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step3-224x94.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step3-336x140.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step3-504x210.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step3-672x281.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step3-400x167.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step3-600x251.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step3-800x334.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step3-944x394.png 944w\" sizes=\"(max-width: 982px) 100vw, 982px\" \/><\/figure>\n<\/div>\n\n\n<p>Und im letzten Schritt werden die zwei Teil-Arrays [1, 3, 7, 8] und [2, 4, 5, 6, 9] zum Endergebnis zusammengef\u00fchrt:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"982\" height=\"410\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step4.png\" alt=\"Mergesort Beispiel: Merge Schritt 4\" class=\"wp-image-15162\" style=\"width:491px;height:205px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step4.png 982w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step4-224x94.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step4-336x140.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step4-504x210.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step4-672x281.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step4-400x167.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step4-600x251.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step4-800x334.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge_step4-944x394.png 944w\" sizes=\"(max-width: 982px) 100vw, 982px\" \/><\/figure>\n<\/div>\n\n\n<p>Am Ende erhalten wir das sortierte Array [1, 2, 3, 4, 5, 6, 7, 8, 9]. Das folgende Diagramm zeigt alle Merge-Schritte zusammengefasst in einer \u00dcbersicht:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"982\" height=\"930\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge-all-steps.png\" alt=\"Mergesort Beispiel: Alle Merge-Schritte\" class=\"wp-image-15163\" style=\"width:491px;height:465px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge-all-steps.png 982w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge-all-steps-224x212.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge-all-steps-336x318.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge-all-steps-504x477.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge-all-steps-672x636.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge-all-steps-400x379.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge-all-steps-600x568.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge-all-steps-800x758.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_example_merge-all-steps-944x894.png 944w\" sizes=\"(max-width: 982px) 100vw, 982px\" \/><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"mergesort-java-quellcode\">Mergesort Java Quellcode<\/h2>\n\n\n\n<p>Im folgenden findest du die einfachste Implementierung von Mergesort.<\/p>\n\n\n\n<p>Zun\u00e4chst ruft die Methode <code>sort()<\/code> die Methode <code>mergeSort()<\/code> auf und \u00fcbergibt dieser das Array sowie dessen Start- und Endpositionen.<\/p>\n\n\n\n<p><code>mergeSort()<\/code> pr\u00fcft, ob es f\u00fcr ein Teil-Array der L\u00e4nge 1 aufgerufen wurde und, wenn ja, gibt eine Kopie dieses Teil-Arrays zur\u00fcck. <\/p>\n\n\n\n<p>Anderfalls wird das Array geteilt, und <code>mergeSort()<\/code> wird rekursiv f\u00fcr beide Teile aufgerufen. Die beiden Aufrufe liefern jeweils ein sortiertes Array zur\u00fcck. Diese werden anschlie\u00dfend durch Aufruf der <code>merge()<\/code>-Methode zusammengef\u00fchrt, und <code>mergeSort()<\/code> gibt dieses zusammengef\u00fchrte, sortierte Array zur\u00fcck.<\/p>\n\n\n\n<p>Abschlie\u00dfend kopiert die <code>sort()<\/code>-Methode das sortierte Array zur\u00fcck in das Eingabe-Array. Man k\u00f6nnte das sortierte Array auch direkt zur\u00fcckgeben \u2013 das w\u00e4re allerdings inkompatibel zum Test-Framework.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">MergeSort<\/span> <\/span>{\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">sort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> length = elements.length;\n    <span class=\"hljs-keyword\">int<\/span>&#091;] sorted = mergeSort(elements, <span class=\"hljs-number\">0<\/span>, length - <span class=\"hljs-number\">1<\/span>);\n    System.arraycopy(sorted, <span class=\"hljs-number\">0<\/span>, elements, <span class=\"hljs-number\">0<\/span>, length);\n  }\n\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;] mergeSort(<span class=\"hljs-keyword\">int<\/span>&#091;] elements, <span class=\"hljs-keyword\">int<\/span> left, <span class=\"hljs-keyword\">int<\/span> right) {\n    <span class=\"hljs-comment\">\/\/ End of recursion reached?<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (left == right) <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;]{elements&#091;left]};\n\n    <span class=\"hljs-keyword\">int<\/span> middle = left + (right - left) \/ <span class=\"hljs-number\">2<\/span>;\n    <span class=\"hljs-keyword\">int<\/span>&#091;] leftArray = mergeSort(elements, left, middle);\n    <span class=\"hljs-keyword\">int<\/span>&#091;] rightArray = mergeSort(elements, middle + <span class=\"hljs-number\">1<\/span>, right);\n    <span class=\"hljs-keyword\">return<\/span> merge(leftArray, rightArray);\n  }\n\n  <span class=\"hljs-keyword\">int<\/span>&#091;] merge(<span class=\"hljs-keyword\">int<\/span>&#091;] leftArray, <span class=\"hljs-keyword\">int<\/span>&#091;] rightArray) {\n    <span class=\"hljs-keyword\">int<\/span> leftLen = leftArray.length;\n    <span class=\"hljs-keyword\">int<\/span> rightLen = rightArray.length;\n\n    <span class=\"hljs-keyword\">int<\/span>&#091;] target = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;leftLen + rightLen];\n    <span class=\"hljs-keyword\">int<\/span> targetPos = <span class=\"hljs-number\">0<\/span>;\n    <span class=\"hljs-keyword\">int<\/span> leftPos = <span class=\"hljs-number\">0<\/span>;\n    <span class=\"hljs-keyword\">int<\/span> rightPos = <span class=\"hljs-number\">0<\/span>;\n\n    <span class=\"hljs-comment\">\/\/ As long as both arrays contain elements...<\/span>\n    <span class=\"hljs-keyword\">while<\/span> (leftPos &lt; leftLen &amp;&amp; rightPos &lt; rightLen) {\n      <span class=\"hljs-comment\">\/\/ Which one is smaller?<\/span>\n      <span class=\"hljs-keyword\">int<\/span> leftValue = leftArray&#091;leftPos];\n      <span class=\"hljs-keyword\">int<\/span> rightValue = rightArray&#091;rightPos];\n      <span class=\"hljs-keyword\">if<\/span> (leftValue &lt;= rightValue) {\n        target&#091;targetPos++] = leftValue;\n        leftPos++;\n      } <span class=\"hljs-keyword\">else<\/span> {\n        target&#091;targetPos++] = rightValue;\n        rightPos++;\n      }\n    }\n    <span class=\"hljs-comment\">\/\/ Copy the rest<\/span>\n    <span class=\"hljs-keyword\">while<\/span> (leftPos &lt; leftLen) {\n      target&#091;targetPos++] = leftArray&#091;leftPos++];\n    }\n    <span class=\"hljs-keyword\">while<\/span> (rightPos &lt; rightLen) {\n      target&#091;targetPos++] = rightArray&#091;rightPos++];\n    }\n    <span class=\"hljs-keyword\">return<\/span> target;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Den Quellcode findest Du hier <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/mergesort\/MergeSort.java\" target=\"_blank\">im GitHub-Repository<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"mergesort-zeitkomplexitaet\">Mergesort Zeitkomplexit\u00e4t<\/h2>\n\n\n\n<p>(Die Begriffe \u201eZeitkomplexit\u00e4t\u201c und \u201eO-Notation\u201c werden&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">in diesem Artikel<\/a>&nbsp;anhand von Beispielen und Diagrammen erkl\u00e4rt.)<\/p>\n\n\n\n<p>Wir bezeichnen die Anzahl der Elemente mit&nbsp;<em>n<\/em>.<\/p>\n\n\n\n<p>Da wir die (Sub-)Arrays immer wieder in zwei gleich gro\u00dfe Teile aufteilen, ben\u00f6tigen wir bei einer Verdopplung der Anzahl der Elemente&nbsp;<em>n<\/em>&nbsp;nur eine einzige zus\u00e4tzliche Stufe von Teilungen <em>d<\/em>. Folgendes Diagramm demonstriert, dass bei vier Elementen zwei Teilungsstufen ben\u00f6tigt werden und bei acht Elementen nur eine mehr:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1102\" height=\"562\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_divide.png\" alt=\"Mergesort Zeitkomplexit\u00e4t - Anzahl der Teilungsstufen\" class=\"wp-image-15214\" style=\"width:551px;height:281px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_divide.png 1102w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_divide-224x114.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_divide-336x171.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_divide-504x257.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_divide-672x343.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_divide-400x204.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_divide-600x306.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_divide-800x408.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_divide-944x481.png 944w\" sizes=\"(max-width: 1102px) 100vw, 1102px\" \/><\/figure>\n<\/div>\n\n\n<p>Somit betr\u00e4gt die Anzahl der Teilungsstufen <em>log<sub>2<\/sub> n<\/em>.<\/p>\n\n\n\n<p>Auf jeder Merge-Stufe m\u00fcssen wir insgesamt&nbsp;<em>n<\/em>&nbsp;Elemente zusammenf\u00fchren (auf der ersten <em>n \u00d7 1<\/em>, auf der zweiten Stufe <em>n\/2 \u00d7 2<\/em>, auf der dritten Stufe <em>n\/4 \u00d7 4<\/em>, usw.):<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1224\" height=\"658\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_merge.png\" alt=\"Mergesort Zeitkomplexit\u00e4t - Aufwand pro Teilungsstufe\" class=\"wp-image-15185\" style=\"width:612px;height:329px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_merge.png 1224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_merge-224x120.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_merge-336x181.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_merge-504x271.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_merge-672x361.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_merge-400x215.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_merge-600x323.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_merge-800x430.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_merge-944x507.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_time_complexity_merge-1200x645.png 1200w\" sizes=\"(max-width: 1224px) 100vw, 1224px\" \/><\/figure>\n<\/div>\n\n\n<p>Der Merge-Vorgang enth\u00e4lt keine verschachtelten Schleifen, erfolgt also mit linearem Aufwand: Bei Verdoppelung der Array-Gr\u00f6\u00dfe verdoppelt sich auch der Merge-Aufwand. Der Gesamtaufwand ist daher auf allen Merge-Stufen gleich.<\/p>\n\n\n\n<p>Wir haben also&nbsp;<em>n<\/em>&nbsp;Elemente mal&nbsp;<em>log<sub>2<\/sub>&nbsp;n<\/em>&nbsp;Teilungs- und Merge-Stufen. Damit gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Die Zeitkomplexit\u00e4t von Mergesort betr\u00e4gt:&nbsp;<em>O(n log n)<\/em><\/p>\n\n\n\n<p>Und zwar unabh\u00e4ngig davon, ob die Eingabeelemente vorsortiert sind oder nicht. Mergesort ist also f\u00fcr sortierte Eingabeelemente nicht schneller als f\u00fcr zuf\u00e4llig angeordnete.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-des-java-mergesort-beispiels\">Laufzeit des Java Mergesort-Beispiels<\/h3>\n\n\n\n<p>Genug der Theorie! Das Testprogramm <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/UltimateTest.java\" target=\"_blank\" rel=\"noopener\">UltimateTest<\/a> misst die Laufzeit von Mergesort (und aller anderen Sortieralgorithmen dieser Artikelserie). Es geht dazu wie folgt vor:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Sortiert werden Arrays der L\u00e4nge 1.024, 2.048, 4.096, usw... bis maximal 536.870.912 (= 2<sup>29<\/sup>) oder so lange, bis ein Sortiervorgang l\u00e4nger als 20 Sekunden dauert.<\/li>\n\n\n\n<li>Sortiert werden mit Zufallszahlen gef\u00fcllte Arrays, sowie aufsteigend und absteigend vorsortierte Zahlenfolgen.<\/li>\n\n\n\n<li>In zwei WarmUp-Runden wird dem HotSpot-Compiler ausreichend Zeit gegeben, den Code zu optimieren.<\/li>\n<\/ul>\n\n\n\n<p>Die Tests werden solange wiederholt, bis der Prozess abgebrochen wird. Hier ist das Ergebnis f\u00fcr Mergesort nach 50 Wiederholungen (dies ist der \u00dcbersicht halber nur ein Auszug; das vollst\u00e4ndige Ergebnis&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-05-30\/Test_Results_Mergesort.txt\" target=\"_blank\">findest du hier<\/a>):<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-right\" data-align=\"right\">n<\/th><th class=\"has-text-align-right\" data-align=\"right\">unsortiert<\/th><th class=\"has-text-align-right\" data-align=\"right\">aufsteigend<\/th><th class=\"has-text-align-right\" data-align=\"right\">absteigend<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-right\" data-align=\"right\">1.024<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,069 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,032 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,033 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">2.048<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,141 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,053 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,056 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">4.096<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,297 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,109 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,116 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">8.192<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,604 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,213 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,228 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">33.554.432<\/td><td class=\"has-text-align-right\" data-align=\"right\">4.860,2 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.954,7 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.040,2 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">67.108.864<\/td><td class=\"has-text-align-right\" data-align=\"right\">9.623,2 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">3.622,8 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">3.815,7 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">134.217.728<\/td><td class=\"has-text-align-right\" data-align=\"right\">19.700,3 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">6.542,1 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">6.973,0 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">268.435.456<\/td><td class=\"has-text-align-right\" data-align=\"right\">40.852,4 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">13.773,5 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">14.708,2 ms<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Hier die Messwerte als Diagramm:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1504\" height=\"874\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_runtime.png\" alt=\"Mergesort Laufzeit f\u00fcr sortierte und unsortierte Elemente\" class=\"wp-image-15222\" style=\"width:752px;height:437px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_runtime.png 1504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_runtime-224x130.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_runtime-336x195.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_runtime-504x293.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_runtime-672x391.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_runtime-400x232.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_runtime-600x349.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_runtime-800x465.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_runtime-944x549.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_runtime-1200x697.png 1200w\" sizes=\"(max-width: 1504px) 100vw, 1504px\" \/><\/figure>\n<\/div>\n\n\n<p>Es l\u00e4sst sich sehr gut sehen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Die Laufzeit w\u00e4chst in allen F\u00e4llen etwa linear mit der Anzahl der Elemente, entspricht also dem erwarteten quasi-linearen Aufwand \u2013 <em>O(n log n)<\/em>.<\/li>\n\n\n\n<li>F\u00fcr vorsortierte Elemente ist Mergesort etwa dreimal schneller als f\u00fcr unsortierte Elemente.<\/li>\n\n\n\n<li>F\u00fcr absteigend vorsortierte Elemente ben\u00f6tigt Mergesort etwas mehr Zeit als f\u00fcr aufsteigend sortierte Elemente.<\/li>\n<\/ul>\n\n\n\n<p>Wie lassen sich diese Unterschiede erkl\u00e4ren?<\/p>\n\n\n\n<p>Mit dem Programm&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/CountOperations.java\" target=\"_blank\">CountOperations<\/a>&nbsp;k\u00f6nnen wir die Anzahl der Operationen f\u00fcr die verschiedenen F\u00e4lle messen lassen. Die Anzahl der Schreiboperationen ist f\u00fcr alle F\u00e4lle gleich, da der Merge-Prozess \u2013 unabh\u00e4ngig von der Vorsortierung \u2013 alle Elemente der Teil-Arrays in ein neues Array kopiert. <\/p>\n\n\n\n<p>Die Anzahl der Vergleiche unterscheidet sich jedoch; du findest sie in der folgenden Tabelle gegen\u00fcbergestellt (das vollst\u00e4ndige Ergebnis findest Du in der Datei <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-07-30\/CountOperations_Mergesort.log\">CountOperations_Mergesort.log<\/a>):<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-right\" data-align=\"right\">n<\/th><th class=\"has-text-align-right\" data-align=\"right\">Vergleiche<br>unsortiert<\/th><th class=\"has-text-align-right\" data-align=\"right\">Vergleiche<br>aufsteigend<\/th><th class=\"has-text-align-right\" data-align=\"right\">Vergleiche<br>absteigend<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">1.024<\/td><td class=\"has-text-align-right\" data-align=\"right\">31.719<\/td><td class=\"has-text-align-right\" data-align=\"right\">23.549<\/td><td class=\"has-text-align-right\" data-align=\"right\">24.572<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">2.048<\/td><td class=\"has-text-align-right\" data-align=\"right\">69.520<\/td><td class=\"has-text-align-right\" data-align=\"right\">51.197<\/td><td class=\"has-text-align-right\" data-align=\"right\">53.244<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">4.096<\/td><td class=\"has-text-align-right\" data-align=\"right\">151.515<\/td><td class=\"has-text-align-right\" data-align=\"right\">110.589<\/td><td class=\"has-text-align-right\" data-align=\"right\">114.684<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">8.192<\/td><td class=\"has-text-align-right\" data-align=\"right\">327.517<\/td><td class=\"has-text-align-right\" data-align=\"right\">237.565<\/td><td class=\"has-text-align-right\" data-align=\"right\">245.756<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">16.384<\/td><td class=\"has-text-align-right\" data-align=\"right\">703.896<\/td><td class=\"has-text-align-right\" data-align=\"right\">507.901<\/td><td class=\"has-text-align-right\" data-align=\"right\">524.284<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\">Laufzeitunterschied aufsteigend \/ absteigend sortierte Elemente<\/h4>\n\n\n\n<p>Der Unterschied zwischen aufsteigend und absteigend sortierten Elementen entspricht in etwa dem gemessenen Zeitunterschied. Der Grund f\u00fcr den Unterschied liegt in dieser Code-Zeile:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">while<\/span> (leftPos &lt; leftLen &amp;&amp; rightPos &lt; rightLen)<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Bei aufsteigend sortierten Elementen werden zuerst alle Elemente des <em>linken<\/em> Teil-Arrays in das Ziel-Array kopiert, so dass <code>leftPos &lt; leftLen<\/code> als erstes <code>false<\/code> ergibt und danach der rechte Term nicht mehr ausgewertet werden muss.<\/p>\n\n\n\n<p>Bei absteigend sortierten Elementen werden zuerst alle Elemente des <em>rechten<\/em> Teil-Arrays kopiert, so dass <code>rightPos &lt; rightLen<\/code> zuerst <code>false<\/code> ergibt. Da dieser Vergleich <em>nach<\/em> <code>leftPos &lt; leftLen<\/code> ausgef\u00fchrt wird, wird bei absteigend sortierten Elementen in jeder Merge-Runde einmal mehr der linke Vergleich <code>leftPos &lt; leftLen<\/code> durchgef\u00fchrt.<\/p>\n\n\n\n<p>W\u00fcrden wir die Zeile \u00e4ndern in<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">while<\/span> (rightPos &lt; rightLen &amp;&amp; leftPos &lt; leftLen)<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>... dann w\u00fcrde sich das Laufzeitverh\u00e4ltnis das Sortierens von aufsteigend zu absteigend vorsortierten Elementen entsprechend umkehren.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Laufzeitunterschied sortierte \/ unsortierte Elemente<\/h4>\n\n\n\n<p>Mergesort ist f\u00fcr vorsortierte Elemente etwa drei mal schneller als f\u00fcr unsortierte Elemente. Die Anzahl der Vergleichsoperationen unterscheidet sich allerdings nur um etwa ein Drittel.<\/p>\n\n\n\n<p>Warum f\u00fchrt ein Drittel weniger Operationen zu dreimal schnellerer Abarbeitung?<\/p>\n\n\n\n<p>Die Ursache liegt in der <a rel=\"noopener\" href=\"https:\/\/de.wikipedia.org\/wiki\/Sprungvorhersage\" target=\"_blank\">Sprungvorhersage<\/a>&nbsp;(englisch \u201ebranch prediction\u201c): Wenn die Elemente sortiert sind, dann sind die Resultate der Vergleiche in den Loop- und Branch-Statements<\/p>\n\n\n\n<p class=\"has-text-align-center\"><code>while (leftPos &lt; leftLen &amp;&amp; rightPos &lt; rightLen) <\/code><\/p>\n\n\n\n<p>und<\/p>\n\n\n\n<p class=\"has-text-align-center\"><code>if (leftValue &lt;= rightValue) <\/code><\/p>\n\n\n\n<p>bis zum Ende eines Merge-Vorgangs immer gleich. Somit kann die Befehls-Pipeline der CPU w\u00e4hrend des Mergens voll ausgenutzt werden. <\/p>\n\n\n\n<p>Bei unsortierten Eingabedaten hingegen k\u00f6nnen die Resultate der Vergleiche nicht verl\u00e4sslich vorhergesagt werden. Die Pipeline muss also st\u00e4ndig gel\u00f6scht und neu gef\u00fcllt werden.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"weitere-eigenschaften-von-mergesort\">Weitere Eigenschaften von Mergesort<\/h2>\n\n\n\n<p>Dieses Kapitel behandelt die Platzkomplexit\u00e4t von Mergesort, die Stabilit\u00e4t sowie die Parallelisierbarkeit.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"platzkomplexitaet-von-mergesort\">Platzkomplexit\u00e4t von Mergesort<\/h3>\n\n\n\n<p>In der Merge-Phase werden Elemente aus zwei Teil-Arrays in ein neu erstelltes Ziel-Array kopiert. Im allerletzten Merge-Schritt ist das Ziel-Array genau so gro\u00df wie das zu sortierende Array. Wir haben also einen linearem Platzbedarf: Bei einem doppelt so gro\u00dfen Eingabe-Array verdoppelt sich auch der zus\u00e4tzlich ben\u00f6tigte Speicherplatz. Es gilt also:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Die Platzkomplexit\u00e4t von Mergesort betr\u00e4gt:&nbsp;<em>O(n)<\/em><\/p>\n\n\n\n<p>(Zur Erinnerung: Bei linearem Aufwand kann konstanter Platzbedarf f\u00fcr Hilfs- und Schleifenvariablen vernachl\u00e4ssigt werden.)<\/p>\n\n\n\n<p>Dieser zus\u00e4tzliche Speicherbedarf kann durch sogenannte <em>In-Place<\/em>-Verfahren umgangen werden; diese werden im Abschnitt <a href=\"#In-Place_Mergesort\">\"In-Place Mergesort\"<\/a> behandelt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"stabilitaet-von-mergesort\">Stabilit\u00e4t von Mergesort<\/h3>\n\n\n\n<p>In der Merge-Phase entscheiden wir mittels <code>if (leftValue &lt;= rightValue)<\/code>, ob das n\u00e4chste Element aus dem linken oder rechten Teil-Array in das Ziel-Array kopiert wird. Wenn linker und rechter Wert gleich sind, wird also zuerst der linke kopiert und dann der rechte. Somit bleibt die Reihenfolge gleicher Elemente zueinander immer unver\u00e4ndert.<\/p>\n\n\n\n<p>Mergesort ist demzufolge ein stabiles Sortierverfahren.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"parallelisierbarkeit-von-mergesort\">Parallelisierbarkeit von Mergesort<\/h3>\n\n\n\n<p>Es gibt grunds\u00e4tzlich zwei Ans\u00e4tze, um Mergesort zu parallelisieren:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Rekursive Aufrufe von <code>mergeSort()<\/code> k\u00f6nnen parallel ausgef\u00fchrt werden; hierbei k\u00f6nnen allerdings heutige Mehrkern-CPUs in den letzten Merge-Stufen nicht voll ausgenutzt werden.<\/li>\n\n\n\n<li>Die <code>merge()<\/code>-Methode selbst kann parallelisiert werden.<\/li>\n<\/ul>\n\n\n\n<p>Weiterf\u00fchrende Informationen dazu findest du im <a rel=\"noopener\" href=\"https:\/\/de.wikipedia.org\/wiki\/Mergesort#Paralleler_Mergesort\" target=\"_blank\">Mergesort-Artikel von Wikipedia<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"in-place-mergesort\">In-Place Mergesort<\/h2>\n\n\n\n<p>Im Abschnitt <a href=\"#Platzkomplexitaet_von_Mergesort\">\"Platzkomplexit\u00e4t\"<\/a> haben wir festgestellt, dass Mergesort einen zus\u00e4tzlichen Platzbedarf in der Gr\u00f6\u00dfenordnung <em>O(n)<\/em> hat.<\/p>\n\n\n\n<p>Es gibt verschiedene Ans\u00e4tze, um den Merge-Vorgang ohne zus\u00e4tzlichen Speicher (also \"in place\") auskommen zu lassen.<\/p>\n\n\n\n<p>Ein Ansatz ist folgender: <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Wenn das Element \u00fcber dem linken Merge-Zeiger kleiner oder gleich dem Element \u00fcber dem rechten Merge-Zeiger ist, wird der linke Merge-Zeiger um ein Feld nach rechts verschoben.<\/li>\n\n\n\n<li>Andernfalls werden alle Element vom ersten Zeiger bis zu, aber ausschlie\u00dflich dem zweiten Zeiger um ein Feld nach rechts geschoben und das rechte Element auf den freigewordenen Platz gesetzt. Danach werden <em>beide<\/em> Zeiger um ein Feld nach rechts verschoben, ebenso die Endposition des linken Teil-Arrays.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"in-place-mergesort-beispiel\">In-Place Mergesort \u2013 Beispiel<\/h3>\n\n\n\n<p>Das folgende Beispiel zeigt diesen In-Place-Merge-Algorithmus am Beispiel von oben \u2013 gemerged werden sollen die Teil-Arrays [2, 3, 5] und [1, 4, 6].<\/p>\n\n\n\n<p>Das linke Teil-Array ist gelb eingef\u00e4rbt, das rechte orange und die fertig gemergten Elemente blau.<\/p>\n\n\n\n<p>Im ersten Schritt tritt gleich der zweite Fall ein: Das rechte Element (die 1) ist kleiner als das linke. Es werden alle Elemente des linken Teil-Arrays um ein Feld nach rechts geschoben und das rechte Element wird an den Anfang gesetzt:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1164\" height=\"592\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step1.png\" alt=\"In-place Mergesort - Algorithmus Schritt 1\" class=\"wp-image-15298\" style=\"width:582px;height:296px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step1.png 1164w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step1-224x114.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step1-336x171.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step1-504x256.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step1-672x342.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step1-400x203.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step1-600x305.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step1-800x407.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step1-944x480.png 944w\" sizes=\"(max-width: 1164px) 100vw, 1164px\" \/><\/figure>\n<\/div>\n\n\n<p>Im zweiten Schritt ist das linke Element (die 2) kleiner, daher wird lediglich der linke Suchzeiger ein Feld nach rechts verschoben:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1164\" height=\"564\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step2.png\" alt=\"In-place Mergesort - Algorithmus Schritt 2\" class=\"wp-image-15300\" style=\"width:582px;height:282px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step2.png 1164w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step2-224x109.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step2-336x163.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step2-504x244.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step2-672x326.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step2-400x194.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step2-600x291.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step2-800x388.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step2-944x457.png 944w\" sizes=\"(max-width: 1164px) 100vw, 1164px\" \/><\/figure>\n<\/div>\n\n\n<p>Im dritten Schritt ist wieder das linke Element (die 3) kleiner, es wird also wieder der linke Suchzeiger verschoben:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1164\" height=\"564\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step3.png\" alt=\"In-place Mergesort - Algorithmus Schritt 3\" class=\"wp-image-15301\" style=\"width:582px;height:282px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step3.png 1164w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step3-224x109.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step3-336x163.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step3-504x244.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step3-672x326.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step3-400x194.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step3-600x291.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step3-800x388.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step3-944x457.png 944w\" sizes=\"(max-width: 1164px) 100vw, 1164px\" \/><\/figure>\n<\/div>\n\n\n<p>Im vierten Schritt ist das rechte Element (die 4) kleiner als das linke. Der verbleibende Teil des linken Bereichs (nur noch die 5) wird also um ein Feld nach rechts geschoben und das rechte Element auf den freien Platz gesetzt:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1164\" height=\"592\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step4-v2.png\" alt=\"In-place Mergesort - Algorithmus Schritt 4\" class=\"wp-image-15307\" style=\"width:582px;height:296px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step4-v2.png 1164w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step4-v2-224x114.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step4-v2-336x171.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step4-v2-504x256.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step4-v2-672x342.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step4-v2-400x203.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step4-v2-600x305.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step4-v2-800x407.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step4-v2-944x480.png 944w\" sizes=\"(max-width: 1164px) 100vw, 1164px\" \/><\/figure>\n<\/div>\n\n\n<p>Im f\u00fcnften Schritt ist das linke Element (die 5) kleiner. Der linke Suchzeiger wird um eine Position nach rechts geschoben und hat damit das Ende des linken Bereichs erreicht:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1164\" height=\"564\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step5.png\" alt=\"In-place Mergesort - Algorithmus Schritt 5\" class=\"wp-image-15303\" style=\"width:582px;height:282px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step5.png 1164w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step5-224x109.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step5-336x163.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step5-504x244.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step5-672x326.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step5-400x194.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step5-600x291.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step5-800x388.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/in-place-mergesort-algorithm-step5-944x457.png 944w\" sizes=\"(max-width: 1164px) 100vw, 1164px\" \/><\/figure>\n<\/div>\n\n\n<p>Der In-Place-Merge-Vorgang ist damit abgeschlossen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"in-place-mergesort-zeitkomplexitaet\">In-Place Mergesort \u2013 Zeitkomplexit\u00e4t<\/h3>\n\n\n\n<p>Wir haben die Merge-Phase jetzt zwar ohne zus\u00e4tzlichen Speicherbedarf ausgef\u00fchrt \u2013 allerdings haben wir uns dies teuer erkauft: Durch die zwei verschachtelten Schleifen hat die Merge-Phase nun eine Zeitkomplexit\u00e4t im <em>average<\/em> und <em>worst case<\/em> von <em>O(n\u00b2)<\/em> \u2013 statt vorher <em>O(n)<\/em>.<\/p>\n\n\n\n<p>Die Gesamt-Komplexit\u00e4t des Sortierverfahrens ist damit <em>O(n\u00b2 log n)<\/em> \u2013 statt <em>O(n log n)<\/em>. Der Algorithmus ist somit nicht mehr effizient.<\/p>\n\n\n\n<p>Lediglich im <em>best case<\/em>, wenn die Zahlen vorab aufsteigend sortiert sind, bleibt die Zeitkomplexit\u00e4t innerhalb der Merge-Phase <em>O(n)<\/em> und die des Gesamt-Algorithmus <em>O(n log n)<\/em>. Der Grund daf\u00fcr ist, dass in diesem Fall die innere Schleife, die die Elemente des linken Teilarrays nach rechts verschiebt, nie ausgef\u00fchrt wird.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"in-place-mergesort-quellcode\">In-Place Mergesort \u2013 Quellcode<\/h3>\n\n\n\n<p>Hier ist der Quellcode der <code>merge()<\/code>-Methode von In-Place Mergesort:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">merge<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements, <span class=\"hljs-keyword\">int<\/span> leftPos, <span class=\"hljs-keyword\">int<\/span> rightPos, <span class=\"hljs-keyword\">int<\/span> rightEnd)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">int<\/span> leftEnd = rightPos - <span class=\"hljs-number\">1<\/span>;\n\n  <span class=\"hljs-keyword\">while<\/span> (leftPos &lt;= leftEnd &amp;&amp; rightPos &lt;= rightEnd) {\n    <span class=\"hljs-comment\">\/\/ Which one is smaller?<\/span>\n    <span class=\"hljs-keyword\">int<\/span> leftValue = elements&#091;leftPos];\n    <span class=\"hljs-keyword\">int<\/span> rightValue = elements&#091;rightPos];\n    <span class=\"hljs-keyword\">if<\/span> (leftValue &lt;= rightValue) {\n      leftPos++;\n    } <span class=\"hljs-keyword\">else<\/span> {\n      <span class=\"hljs-comment\">\/\/ Move all the elements from leftPos to excluding rightPos one field<\/span>\n      <span class=\"hljs-comment\">\/\/ to the right<\/span>\n      <span class=\"hljs-keyword\">int<\/span> movePos = rightPos;\n      <span class=\"hljs-keyword\">while<\/span> (movePos &gt; leftPos) {\n        elements&#091;movePos] = elements&#091;movePos - <span class=\"hljs-number\">1<\/span>];\n        movePos--;\n      }\n      elements&#091;leftPos] = rightValue;\n      leftPos++;\n      leftEnd++;\n      rightPos++;\n    }\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Den vollst\u00e4ndigen Quellcode findest du in der Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/mergesort\/InPlaceMergeSort.java\">InPlaceMergeSort<\/a> im GitHub-Repository.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"effiziente-in-place-merge-verfahren\">Effiziente In-Place-Merge-Verfahren<\/h3>\n\n\n\n<p>Es gibt auch effizientere In-Place-Mergeverfahren, die eine Zeitkomplexit\u00e4t von <em>O(n log n)<\/em> erreichen und damit eine Gesamt-Zeitkomplexit\u00e4t von <em>O(n (log n)\u00b2)<\/em>, diese sind jedoch sehr komplex, so dass ich sie hier nicht weiter behandeln werde.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"natural-mergesort\">Natural Mergesort<\/h2>\n\n\n\n<p>Natural Mergesort ist eine Optimierung von Mergesort: Es identifiziert vorsortierte Bereiche (\"runs\") in den Eingabedaten und merged diese jeweils miteinander. So wird das unn\u00f6tige weitere Teilen und Mergen vorsortierter Teilfolgen vermieden. Komplett aufsteigend sortierte Eingabeelemente werden dementsprechend in der Gr\u00f6\u00dfenordnung <em>O(n)<\/em> sortiert.<\/p>\n\n\n\n<p>Je nach Implementierung werden auch absteigend sortierte Teilfolgen (\"descending runs\") erkannt und in umgekehrter Richtung gemerged. Diese Varianten erreichen auch f\u00fcr komplett absteigend sortierte Eingabedaten <em>O(n)<\/em>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"natural-mergesort-beispiel\">Natural Mergesort \u2013 Beispiel<\/h3>\n\n\n\n<p>Die folgende Grafik zeigt Natural Mergesort am Beispiel unserer Zahlenfolge [3, 7, 1, 8, 2, 5, 9, 4, 6]. Im ersten Schritt werden die \"runs\" identifiziert. In den folgenden Schritten werden diese gemerged:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"982\" height=\"758\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/natural_merge_sort_example-v3.png\" alt=\"Natural Mergesort - Beispiel\" class=\"wp-image-15354\" style=\"width:491px;height:379px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/natural_merge_sort_example-v3.png 982w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/natural_merge_sort_example-v3-224x173.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/natural_merge_sort_example-v3-336x259.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/natural_merge_sort_example-v3-504x389.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/natural_merge_sort_example-v3-672x519.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/natural_merge_sort_example-v3-400x309.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/natural_merge_sort_example-v3-600x463.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/natural_merge_sort_example-v3-800x618.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/natural_merge_sort_example-v3-944x729.png 944w\" sizes=\"(max-width: 982px) 100vw, 982px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"natural-mergesort-quellcode\">Natural Mergesort \u2013 Quellcode<\/h3>\n\n\n\n<p>Der folgende Quellcode zeigt eine einfache Implementierung, bei der nur aufsteigend sortierte Bereiche identifiziert und gemerged werden:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">sort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">int<\/span> numElements = elements.length;\n\n  <span class=\"hljs-keyword\">int<\/span>&#091;] tmp = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;numElements];\n  <span class=\"hljs-keyword\">int<\/span>&#091;] starts = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;numElements + <span class=\"hljs-number\">1<\/span>];\n\n  <span class=\"hljs-comment\">\/\/ Step 1: identify runs<\/span>\n  <span class=\"hljs-keyword\">int<\/span> runCount = <span class=\"hljs-number\">0<\/span>;\n  starts&#091;<span class=\"hljs-number\">0<\/span>] = <span class=\"hljs-number\">0<\/span>;\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">1<\/span>; i &lt;= numElements; i++) {\n    <span class=\"hljs-keyword\">if<\/span> (i == numElements || elements&#091;i] &lt; elements&#091;i - <span class=\"hljs-number\">1<\/span>]) {\n      starts&#091;++runCount] = i;\n    }\n  }\n\n  <span class=\"hljs-comment\">\/\/ Step 2: merge runs, until only 1 run is left<\/span>\n  <span class=\"hljs-keyword\">int<\/span>&#091;] from = elements;\n  <span class=\"hljs-keyword\">int<\/span>&#091;] to = tmp;\n\n  <span class=\"hljs-keyword\">while<\/span> (runCount &gt; <span class=\"hljs-number\">1<\/span>) {\n    <span class=\"hljs-keyword\">int<\/span> newRunCount = <span class=\"hljs-number\">0<\/span>;\n\n    <span class=\"hljs-comment\">\/\/ Merge two runs each<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; runCount - <span class=\"hljs-number\">1<\/span>; i += <span class=\"hljs-number\">2<\/span>) {\n      merge(from, to, starts&#091;i], starts&#091;i + <span class=\"hljs-number\">1<\/span>], starts&#091;i + <span class=\"hljs-number\">2<\/span>]);\n      starts&#091;newRunCount++] = starts&#091;i];\n    }\n\n    <span class=\"hljs-comment\">\/\/ Odd number of runs? Copy the last one<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (runCount % <span class=\"hljs-number\">2<\/span> == <span class=\"hljs-number\">1<\/span>) {\n      <span class=\"hljs-keyword\">int<\/span> lastStart = starts&#091;runCount - <span class=\"hljs-number\">1<\/span>];\n      System.arraycopy(from, lastStart, to, lastStart,\n            numElements - lastStart);\n      starts&#091;newRunCount++] = lastStart;\n    }\n\n    <span class=\"hljs-comment\">\/\/ Prepare for next round...<\/span>\n    starts&#091;newRunCount] = numElements;\n    runCount = newRunCount;\n\n    <span class=\"hljs-comment\">\/\/ Swap \"from\" and \"to\" arrays<\/span>\n    <span class=\"hljs-keyword\">int<\/span>&#091;] help = from;\n    from = to;\n    to = help;\n  }\n\n  <span class=\"hljs-comment\">\/\/ If final run is not in \"elements\", copy it there<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (from != elements) {\n    System.arraycopy(from, <span class=\"hljs-number\">0<\/span>, elements, <span class=\"hljs-number\">0<\/span>, numElements);\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die Signatur der <code>merge()<\/code>-Methode unterscheidet sich hier wie folgt vom Beispiel oben:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Anstatt von Teil-Arrays wird hier das gesamte Ursprungs-Arrays sowie Positionsangaben der zu mergenden Bereiche \u00fcbergeben.<\/li>\n\n\n\n<li>Anstatt ein neues Array zur\u00fcckzugeben, wird auch das Ziel-Array zum Bef\u00fcllen an die Methode \u00fcbergeben.<\/li>\n<\/ul>\n\n\n\n<p>Der eigentliche Merge-Algorithmus bleibt der gleiche.<\/p>\n\n\n\n<p>Den vollst\u00e4ndigen Quellcode einschlie\u00dflich der <code>merge()<\/code>-Methode findest du in der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/mergesort\/NaturalMergeSort.java\" target=\"_blank\">NaturalMergeSort im GitHub-Repository<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"timsort\">Timsort<\/h2>\n\n\n\n<p>Das von Tim Peters entwickelte <a rel=\"noopener\" href=\"https:\/\/bugs.python.org\/file4451\/timsort.txt\" target=\"_blank\">Timsort<\/a> ist eine hoch optimierte Weiterentwicklung von Natural Mergesort, bei der unter anderem (Teil-)Arrays bis zu einer bestimmten Gr\u00f6\u00dfe mit Insertion Sort sortiert werden.<\/p>\n\n\n\n<p>Timsort ist der Standard-Sortieralgorithmus in Python. Im JDK wird es f\u00fcr alle nicht-primitiven Objekte verwendet, also in den folgenden Methoden:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>Collections.sort\u200b(List&lt;T&gt; list)<\/code><\/li>\n\n\n\n<li><code>Collections.sort\u200b(List&lt;T&gt; list, Comparator&lt;? super T&gt; c)<\/code><\/li>\n\n\n\n<li><code>List.sort(Comparator&lt;? super E&gt; c)<\/code><\/li>\n\n\n\n<li><code>Arrays.sort(T[] a, Comparator&lt;? super T&gt; c)<\/code><\/li>\n\n\n\n<li><code>Arrays.sort(T[] a, int fromIndex, int toIndex, Comparator&lt;? super T&gt; c)<\/code><\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"mergesort-vs-quicksort\">Mergesort vs. Quicksort<\/h2>\n\n\n\n<p>Wie schl\u00e4gt sich Mergesort im Vergleich zu den im vorangegangenen Artikel behandelten <a href=\"\/de\/algorithmen\/quicksort\/\">Quicksort<\/a>?<\/p>\n\n\n\n<p>Das folgende Diagramm zeigt die Laufzeiten f\u00fcr <em>unsortierte<\/em> und <em>aufsteigend<\/em> sortierte Eingabedaten. <em>Absteigend<\/em> vorsortierte Elemente werden von beiden Algorithmen minimal langsamer verarbeitet als aufsteigend vorsortierte, ich habe sie deshalb der \u00dcbersichtlichkeit halber nicht in das Diagramm eingetragen.<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1504\" height=\"874\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_vs_quicksort_runtime.png\" alt=\"Mergesort vs. Quicksort: Laufzeit f\u00fcr sortierte und unsortierte Elemente\" class=\"wp-image-15234\" style=\"width:752px;height:437px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_vs_quicksort_runtime.png 1504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_vs_quicksort_runtime-224x130.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_vs_quicksort_runtime-336x195.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_vs_quicksort_runtime-504x293.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_vs_quicksort_runtime-672x391.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_vs_quicksort_runtime-400x232.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_vs_quicksort_runtime-600x349.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_vs_quicksort_runtime-800x465.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_vs_quicksort_runtime-944x549.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/mergesort_vs_quicksort_runtime-1200x697.png 1200w\" sizes=\"(max-width: 1504px) 100vw, 1504px\" \/><\/figure>\n<\/div>\n\n\n<p>Quicksort ist f\u00fcr eine Viertelmilliarde unsortierte Elemente etwa 50 % schneller als Mergesort. F\u00fcr vorsortierte Elemente ist es sogar vier mal so schnell.<\/p>\n\n\n\n<p>Der Grund liegt ganz einfach darin, dass beim Mergen immer <em>alle<\/em> Elemente kopiert werden. Bei Quicksort hingegen werden nur diejenigen Elemente verschoben, die sich in der falschen Partition befinden.<\/p>\n\n\n\n<p>Mergesort hat gegen\u00fcber Quicksort den Vorteil, dass auch im&nbsp;<em>worst case<\/em>&nbsp;die Zeitkomplexit\u00e4t&nbsp;<em>O(n log n)<\/em>&nbsp;nicht \u00fcberschritten wird und dass es stabil ist. Diese Vorteile erkauft man sich durch schlechtere Performance und einen zus\u00e4tzlichen Platzbedarf in der Gr\u00f6\u00dfenordnung&nbsp;<em>O(n)<\/em>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zusamenfassung\">Zusamenfassung<\/h2>\n\n\n\n<p>Mergesort ist ein effizienter, stabiler Sortieralgorithmus mit einer Zeitkomplexit\u00e4t von&nbsp;<em>O(n log n)<\/em>&nbsp;im&nbsp;<em>best<\/em>, <em>average<\/em> und <em>worst case<\/em>.<\/p>\n\n\n\n<p>Mergesort hat in seiner Standardimplementierung eine zus\u00e4tzliche Platzkomplexit\u00e4t von <em>O(n)<\/em> \u2013 diese kann durch eine <em>In-Place-Sortierung<\/em> umgangen werden, welche allerdings entweder sehr komplex ist oder die Zeitkomplexit\u00e4t des Algorithmus gravierend verschlechtert.<\/p>\n\n\n\n<p>Die JDK-Methoden <code>Collections.sort()<\/code>, <code>List.sort()<\/code> und&nbsp;<code>Arrays.sort()<\/code>&nbsp;(letzteres f\u00fcr alle nicht-primitiven Objekte) verwenden <em>Timsort<\/em>: ein optimiertes Natural Mergesort, wobei vorsortierte Bereiche in den Eingabedaten erkannt und nicht weiter geteilt werden.<\/p>\n<aside><p>Wenn dir der Artikel weitergeholfen hat, w\u00fcrde ich mich sehr \u00fcber eine positive Bewertung auf meinem <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">ProvenExpert-Profil<\/a> freuen. Dein Feedback hilft mir, meine Inhalte weiter zu verbessern und motiviert mich, neue informative Artikel zu schreiben.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">Bewertung abgeben<\/a><\/p>\r\n                        <p>M\u00f6chtest du auf dem Laufenden bleiben und informiert werden, wenn neue Artikel auf HappyCoders.eu ver\u00f6ffentlicht werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders-Newsletter anzumelden.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"#\" data-formkit-toggle=\"d8ee997126\">Newsletter-Anmeldung<\/a><\/p><\/aside>","protected":false},"excerpt":{"rendered":"<p>Dieser Artikel beschreibt die Funktionsweise von Mergesort, zeigt den Java-Quellcode und erkl\u00e4rt, wie man die Zeitkomplexit\u00e4t bestimmt.<\/p>\n","protected":false},"author":1,"featured_media":43246,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Wie funktioniert Mergesort? Mit Illustrationen und Quellcode. Wie bestimmt man die Zeitkomplexit\u00e4t (ohne komplizierte Mathematik)?","_seopress_robots_index":"","_uag_custom_page_level_css":"","_wp_convertkit_post_meta":{"form":"-1","landing_page":"","tag":"0","restrict_content":"0"},"_metis_text_type":"standard","_metis_text_length":21961,"_post_count":0,"footnotes":""},"categories":[127],"tags":[129],"class_list":["post-12215","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-sortieralgorithmen"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/merge-sort-java-feature-image.jpg",1770,986,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":0,"uagb_excerpt":"Dieser Artikel beschreibt die Funktionsweise von Mergesort, zeigt den Java-Quellcode und erkl\u00e4rt, wie man die Zeitkomplexit\u00e4t bestimmt.","public_identification_id":"87fe8261f7e74ad1a86ac10e44041261","private_identification_id":"3f2d19f26aac47b5bcc10c2ebd11ab67","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12215","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=12215"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12215\/revisions"}],"predecessor-version":[{"id":54126,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12215\/revisions\/54126"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/43246"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=12215"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=12215"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=12215"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}