{"id":4826,"date":"2024-08-05T13:00:56","date_gmt":"2024-08-05T13:00:56","guid":{"rendered":"https:\/\/msgprogramator.sk\/?p=4826"},"modified":"2026-02-17T11:41:35","modified_gmt":"2026-02-17T11:41:35","slug":"merge-sort","status":"publish","type":"post","link":"https:\/\/msgprogramator.sk\/de\/merge-sort\/","title":{"rendered":"Merge sort &#8211; Sortieren durch Aufteilen und Zusammenf\u00fchren in Java"},"content":{"rendered":"<p>Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung ist sehr wichtig f\u00fcr die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten ben\u00f6tigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus h\u00e4ngt von Faktoren wie der Gr\u00f6\u00dfe und den Eigenschaften der Eingabedaten, dem verf\u00fcgbaren Speicher und den Zeit- und Platzanforderungen ab. Um dir die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erkl\u00e4ren und sie in Java programmieren. Bislang haben wir die folgenden Sortieralgorithmen behandelt:<\/p>\n<ul>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/sortieralgorithmen\/\" target=\"_blank\" rel=\"noopener\">Sortieralgorithmen<\/a>: eine Einf\u00fchrung in das Sortieren von Daten,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/bubble-sort\/\" target=\"_blank\" rel=\"noopener\">Bubble sort<\/a> &#8211; Blasen-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/comb-sort\/\" target=\"_blank\" rel=\"noopener\">Comb sort<\/a> &#8211; Kamm-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/big-o-notation\/\" target=\"_blank\" rel=\"noopener\">Big O Notation<\/a>: Analyse der Komplexit\u00e4t von Algorithmen,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/selection-sort\/\" target=\"_blank\" rel=\"noopener\">Selection sort<\/a> &#8211; triedenie v\u00fdberom.<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/insertion-sort\/\" target=\"_blank\" rel=\"noopener\">Insertion sort<\/a> \u2013 Sortieren durch Einf\u00fcgen<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/counting-sort\/\" target=\"_blank\" rel=\"noopener\">Counting sort<\/a> &#8211; Sortieren durch Z\u00e4hlen<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/heap-sort\/\" target=\"_blank\" rel=\"noopener\">Heap sort <\/a> \u2013 Heap-Sortierung<\/li>\n<\/ul>\n<p>Heute werden wir uns mit dem Sortieren durch Zusammenf\u00fchren \u2013 <strong>Merge Sort <\/strong> \u2013 befassen.<\/p>\n<h2>Merge sort<\/h2>\n<p>Merge Sort ist ein sehr effizienter stabiler Sortieralgorithmus, der 1945 von John von Neumann, einem der Pioniere auf dem Gebiet der Informatik, erfunden wurde. Der Grundgedanke dabei ist, dass wir bei einem komplexen Problem versuchen, es in kleinere Teile zu zerlegen und diese Teile separat zu l\u00f6sen. Die endg\u00fcltige L\u00f6sung ist also das Ergebnis der L\u00f6sung jedes der kleineren Teilprobleme. Eine solche Zerlegung von Problemen kann dann perfekt parallelisiert und auf modernen Mehrkernprozessoren effizient gel\u00f6st werden. Wir unterteilen den Eingabedatenvektor in mehrere ann\u00e4hernd gleiche Teile. Die gebr\u00e4uchlichste Version verwendet eine 2-teilige Partitionierung, das ist eine bin\u00e4re Zusammenf\u00fchrung, im Falle von mehreren Teilen ist es eine sogenannte <a href=\"https:\/\/en.wikipedia.org\/wiki\/K-way_merge_algorithm\" target=\"_blank\" rel=\"nofollow noopener\">K-way Zusammenf\u00fchrung<\/a>. Sehen wir uns an, wie diese Technik bei der Datensortierung eingesetzt werden kann.<\/p>\n<h2>Merge sort Algorithmus &#8211; Funktionsprinzip<\/h2>\n<p>Die Eingabedaten werden in etwa zwei gleiche Teile geteilt. Wenn die Anzahl der Elemente ungerade ist, enth\u00e4lt der erste Teil 1 Element mehr. Jeder dieser Teile des Arrays wird weiter in zwei H\u00e4lften geteilt und dies wird wiederholt, bis der Teil nur noch ein Element enth\u00e4lt. Dabei wird ein rekursiver Aufruf verwendet. Ein Array mit einem Element wird als sortiert betrachtet. Sobald die Teile nicht mehr geteilt werden k\u00f6nnen, werden die letzten beiden H\u00e4lften genommen und ihre Elemente zusammengef\u00fchrt, so dass die resultierende Liste ebenfalls sortiert bleibt. Dies wird so lange wiederholt, bis der urspr\u00fcngliche Datenvektor in sortierter Form erhalten wird. Dies l\u00e4sst sich am besten anhand des Beispiels in der folgenden Abbildung nachvollziehen.<\/p>\n<figure id=\"attachment_4043\" aria-describedby=\"caption-attachment-4043\" style=\"width: 890px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-4041 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/algoritmus-merge-sortu-890-850.webp\" alt=\"Visuelle Darstellung des merge sort Algorithmus. Der rote Teil ist die Aufteilungsphase und der gr\u00fcne Teil ist die Zusammenf\u00fchrungsphase. Quelle wikipedia \" width=\"890\" height=\"850\" srcset=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/algoritmus-merge-sortu-890-850.webp 890w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/algoritmus-merge-sortu-890-850-300x287.webp 300w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/algoritmus-merge-sortu-890-850-768x733.webp 768w\" sizes=\"auto, (max-width: 890px) 100vw, 890px\" \/><figcaption id=\"caption-attachment-4043\" class=\"wp-caption-text\">Visuelle Darstellung des merge sort Algorithmus. Der rote Teil ist die Aufteilungsphase und der gr\u00fcne Teil ist die Zusammenf\u00fchrungsphase. Quelle wikipedia<\/figcaption><\/figure>\n<h2>Merge sort Animation, Visualisierung, gif<\/h2>\n<p>Die Animation f\u00fcr merge sort sieht so aus:<\/p>\n<figure id=\"attachment_4046\" aria-describedby=\"caption-attachment-4046\" style=\"width: 344px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-4044 \" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/Merge_sort_animation2.gif\" alt=\"CobaltBlue, CC BY-SA 4.0, via Wikimedia Commons\" width=\"344\" height=\"291\" \/><figcaption id=\"caption-attachment-4046\" class=\"wp-caption-text\">CobaltBlue, CC BY-SA 4.0, via Wikimedia Commons<\/figcaption><\/figure>\n<p>Quelle: commons.wikimedia.org\/wiki\/Category:Animations_of_sort_algorithms<\/p>\n<p>Eine Animation des Algorithmus findest du z.B. auf <a href=\"https:\/\/www.toptal.com\/developers\/sorting-algorithms\" target=\"_blank\" rel=\"nofollow noopener\">Toptal.<\/a> Es gibt 8 Arten von Algorithmen, du kannst die Animation auch r\u00fcckw\u00e4rts abspielen. Auf dieser <a href=\"https:\/\/www.hackerearth.com\/practice\/algorithms\/sorting\/merge-sort\/visualize\/\" target=\"_blank\" rel=\"nofollow noopener\">Seite<\/a> kannst du die Schritte des Algorithmus durchlaufen, so dass du den Zeitverbrauch des Algorithmus \u00fcberpr\u00fcfen kannst.<\/p>\n<h2>Vorteile des Merge sort Algorithmus<\/h2>\n<ul>\n<li>Stabiler Algorithmus<\/li>\n<li>Effizient auch bei gro\u00dfen Datens\u00e4tzen<\/li>\n<li>Kann leicht parallelisiert werden, um die Berechnungslast auf mehrere Prozessoren zu verteilen<\/li>\n<\/ul>\n<h2>Nachteile des Merge sort Algorithmus<\/h2>\n<ul>\n<li>Beim Zusammenf\u00fchren von Subarrays wird zus\u00e4tzlicher Speicherplatz zum Speichern von Daten ben\u00f6tigt<\/li>\n<\/ul>\n<h2>Merge Sort \u2013 Zeitkomplexit\u00e4t<\/h2>\n<table width=\"536\">\n<thead>\n<tr>\n<th rowspan=\"2\" width=\"94\"><strong>Algorithmus<\/strong><\/th>\n<th rowspan=\"2\" width=\"84\"><strong>Methode<\/strong><\/th>\n<th colspan=\"3\" width=\"208\"><strong>Zeitliche Komplexit\u00e4t<\/strong><\/th>\n<th rowspan=\"2\" width=\"82\"><strong>Speicher<\/strong><\/th>\n<th rowspan=\"2\" width=\"69\"><strong>Stabil<\/strong><\/th>\n<\/tr>\n<tr>\n<th width=\"73\"><strong>schlechteste<\/strong><\/th>\n<th width=\"63\"><strong>durchschnittlich<\/strong><\/th>\n<th width=\"71\"><strong>beste<\/strong><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td width=\"94\">Merge sort<\/td>\n<td width=\"84\">merge<\/td>\n<td width=\"73\">O(n log n)<\/td>\n<td width=\"63\">O(n log n)<\/td>\n<td width=\"71\">O(n log n)<\/td>\n<td width=\"82\">O(n)<\/td>\n<td width=\"69\">Ja<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h2>Merge Sort Implementierung, Java Code<\/h2>\n<p>Jetzt werden wir die Implementierung des Merge sort algorithmus in Java zeigen.<\/p>\n<p><strong><u>MergeSort.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">package sorting;\n\npublic class MergeSort {\n    public void sort(int data[], int left, int right)\n    {\n        if (left &lt; right) {\n            \/\/ Find the cutting point\n            int middle = (left + right) \/ 2;\n            \/\/ Sort first and second part separately\n            sort(data, left, middle);\n            sort(data, middle + 1, right);\n            \/\/ Merge both sorted halves\n            merge(data, left, middle, right);\n        }\n    }\n\n    public void merge(int[] data, int left, int middle, int right) {\n        \/\/ Calculate sizes of left and right merge arrays\n        int leftPartSize = middle - left + 1;\n        int rightPartSize = right - middle;\n        \/\/ Create them\n        int[] leftPart = new int[leftPartSize];\n        int[] rightPart = new int[rightPartSize];\n        \/\/ Fill them\n        for (int i = 0; i &lt; leftPartSize; i++) {\n            leftPart[i] = data[left + i];\n        }\n        for (int j = 0; j &lt; rightPartSize; j++) {\n            rightPart[j] = data[middle + 1 + j];\n        }\n\n        System.out.print(&quot;L: &quot;);\n        printArray(leftPart);\n        System.out.print(&quot;+ R: &quot;);\n        printArray(rightPart);\n        System.out.print(&quot;=&gt; &quot;);\n\n        \/\/ k is index of merged array\n        int i = 0, j = 0, k = left;\n        while (i &lt; leftPartSize &amp;&amp; j &lt; rightPartSize) {\n            if (leftPart[i] &lt;= rightPart[j]) {\n                data[k++] = leftPart[i++];\n            }\n            else {\n                data[k++] = rightPart[j++];\n            }\n        }\n        \/\/ Copy any remaining elements\n        while (i &lt; leftPartSize) {\n            data[k++] = leftPart[i++];\n        }\n        while (j &lt; rightPartSize) {\n            data[k++] = rightPart[j++];\n        }\n\n        for (i = left; i &lt; k; i++)\n            System.out.print(data[i] + &quot; &quot;);\n        System.out.println();\n    }\n\n    \/\/ Function to print an array\n    public void printArray(int data[])\n    {\n        for (int i = 0; i &lt; data.length; i++)\n            System.out.print(data[i] + &quot; &quot;);\n        \/\/System.out.println();\n    }\n}<\/code><\/pre>\n<p><strong><u>Main.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">import sorting.MergeSort;\n\npublic class Main {\n    public static void main(String[] args) {\n        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };\n        MergeSort mergeSort = new MergeSort();\n        System.out.print(&quot;Input: &quot;);\n        mergeSort.printArray(dataToSort);\n        System.out.println(&quot;&quot;);\n        mergeSort.sort(dataToSort, 0, dataToSort.length - 1);\n        System.out.print(&quot;Sorted: &quot;);\n        mergeSort.printArray(dataToSort);\n    }\n}<\/code><\/pre>\n<p>Die Ausgabe dieses Beispiels ist:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-medium wp-image-4053\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/vystup-z-prikladu-merge-sort-575-410-300x214.webp\" alt=\"Merge sort Ausgabe aus Beispiel zusammenf\u00fchren\" width=\"300\" height=\"214\" srcset=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/vystup-z-prikladu-merge-sort-575-410-300x214.webp 300w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/vystup-z-prikladu-merge-sort-575-410.webp 575w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausf\u00fchren kannst. Lade <a href=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/MergeSort.zip\" target=\"_blank\" rel=\"noopener\">den <strong>Merge Sort <\/strong> Java-Code<\/a> hier herunter.<\/p>\n<p>Wenn du ein <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/java-entwickler-senior\/\" target=\"_blank\" rel=\"noopener\">Java Programmierer<\/a> bist und nach Arbeit suchst, schau dir unsere <a href=\"https:\/\/msg-life.sk\/de\/mitarbeiter-benefits\/\" target=\"_blank\" rel=\"noopener\">Mitareiterbenefits <\/a> an und reagiere auf die <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/\" target=\"_blank\" rel=\"noopener\">neuesten Stellenangebote<\/a>.<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In diesem Artikel erf\u00e4hrst du, was merge sort ist, ihr Prinzip, ihre Vor- und Nachteile, ihre Visualisierung und ihren Java-Beispielcode.<\/p>\n","protected":false},"author":14,"featured_media":4049,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[57],"tags":[],"class_list":["post-4826","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-java"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4826","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/comments?post=4826"}],"version-history":[{"count":5,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4826\/revisions"}],"predecessor-version":[{"id":9728,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4826\/revisions\/9728"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media\/4049"}],"wp:attachment":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media?parent=4826"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/categories?post=4826"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/tags?post=4826"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}