{"id":34,"date":"2023-06-09T13:12:28","date_gmt":"2023-06-09T13:12:28","guid":{"rendered":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/?page_id=34"},"modified":"2023-11-02T20:24:48","modified_gmt":"2023-11-02T20:24:48","slug":"merge-sort","status":"publish","type":"page","link":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/","title":{"rendered":"Merge Sort"},"content":{"rendered":"<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Merge Sort<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Merge Sort<\/h3>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Merge_sort#\/media\/File:Merge-sort-example-300px.gif\"><img decoding=\"async\" loading=\"lazy\" class=\"size-full wp-image-554 alignright\" src=\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-content\/uploads\/sites\/27\/2023\/11\/merge-sort-animation.gif\" alt=\"\" width=\"600\" height=\"360\" \/><\/a><\/p>\n<p><span style=\"color: #0000ff;\">Time Complexity: O(n log(n)) &#8211; Space Complexity: O(n)<\/span><\/p>\n<p>Merge Sort is a popular sorting algorithm that follows the\u00a0<b>divide and conquer<\/b>\u00a0approach. The algorithm works by breaking down the list into smaller sub-lists and sorting them individually.<\/p>\n<p><strong>Merge sort steps<\/strong><\/p>\n<ol>\n<li>Divide the unsorted list into smaller sub-lists until each sub-list contains only one element.<\/li>\n<li>Repeatedly merge adjacent sub-lists to produce new sorted sub-lists until there is only one sub-list remaining. This is done by comparing the elements of the sub-lists and merging them in the correct order.<\/li>\n<li>The final sorted list is obtained when all sub-lists are merged.<\/li>\n<\/ol>\n<p>Source: Wikipedia\n<\/div><h2 class=\"tabtitle\">Pros &amp; Cons<\/h2>\n<div class=\"tabcontent\">\n<\/p>\n<div class=\"slide-content\">\n<h3>Advantages of Merge Sort<\/h3>\n<ul>\n<li>Merge Sort guarantees a stable sort, which means that the order of equal elements is preserved.<\/li>\n<li>It performs well on large lists and has a time complexity of O(n log n), where n is the number of elements in the list.<\/li>\n<\/ul>\n<h3>Disadvantages of Merge Sort<\/h3>\n<ul>\n<li>It is not an in-place sorting algorithm, meaning it needs extra storage proportional to the size of the input list.<\/li>\n<li>Because it is usually implemented using recursion it can be difficult for beginner programmers to implement and understand.<\/li>\n<\/ul>\n<\/div>\n\n<\/div><h2 class=\"tabtitle\">Python Code<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Python Code<\/h3>\n<p><!-- HTML generated using hilite.me --><\/p>\n<div style=\"background: #ffffff; overflow: auto; width: auto; border: solid gray; border-width: .1em .1em .1em .8em; padding: .2em .6em;\">\n<pre style=\"margin: 0; line-height: 125%;\"><span style=\"color: #0000aa;\">def<\/span> <span style=\"color: #00aa00;\">merge_sort<\/span>(arr):\r\n    <span style=\"color: #0000aa;\">if<\/span> <span style=\"color: #00aaaa;\">len<\/span>(arr) &lt;= <span style=\"color: #009999;\">1<\/span>:\r\n        <span style=\"color: #0000aa;\">return<\/span> arr\r\n\r\n    <span style=\"color: #aaaaaa; font-style: italic;\"># Split the array into two halves<\/span>\r\n    mid = <span style=\"color: #00aaaa;\">len<\/span>(arr) \/\/ <span style=\"color: #009999;\">2<\/span>\r\n    left_half = arr[:mid]\r\n    right_half = arr[mid:]\r\n\r\n    <span style=\"color: #aaaaaa; font-style: italic;\"># Recursively sort both halves<\/span>\r\n    left_half = merge_sort(left_half)\r\n    right_half = merge_sort(right_half)\r\n\r\n    <span style=\"color: #aaaaaa; font-style: italic;\"># Merge the sorted halves<\/span>\r\n    <span style=\"color: #0000aa;\">return<\/span> merge(left_half, right_half)\r\n\r\n<span style=\"color: #0000aa;\">def<\/span> <span style=\"color: #00aa00;\">merge<\/span>(left, right):\r\n    merged = []\r\n    left_index, right_index = <span style=\"color: #009999;\">0<\/span>, <span style=\"color: #009999;\">0<\/span>\r\n\r\n    <span style=\"color: #0000aa;\">while<\/span> left_index &lt; <span style=\"color: #00aaaa;\">len<\/span>(left) <span style=\"color: #0000aa;\">and<\/span> right_index &lt; <span style=\"color: #00aaaa;\">len<\/span>(right):\r\n        <span style=\"color: #0000aa;\">if<\/span> left[left_index] &lt; right[right_index]:\r\n            merged.append(left[left_index])\r\n            left_index += <span style=\"color: #009999;\">1<\/span>\r\n        <span style=\"color: #0000aa;\">else<\/span>:\r\n            merged.append(right[right_index])\r\n            right_index += <span style=\"color: #009999;\">1<\/span>\r\n\r\n    <span style=\"color: #aaaaaa; font-style: italic;\"># Append any remaining elements from both lists (if any)<\/span>\r\n    merged.extend(left[left_index:])\r\n    merged.extend(right[right_index:])\r\n\r\n    <span style=\"color: #0000aa;\">return<\/span> merged\r\n\r\n<span style=\"color: #aaaaaa; font-style: italic;\"># Example usage:<\/span>\r\narr = [<span style=\"color: #009999;\">12<\/span>, <span style=\"color: #009999;\">11<\/span>, <span style=\"color: #009999;\">13<\/span>, <span style=\"color: #009999;\">5<\/span>, <span style=\"color: #009999;\">6<\/span>, <span style=\"color: #009999;\">7<\/span>]\r\nsorted_arr = merge_sort(arr)\r\n<span style=\"color: #0000aa;\">print<\/span>(<span style=\"color: #aa5500;\">\"Sorted array:\"<\/span>, sorted_arr)\r\n<\/pre>\n<\/div>\n\n<\/div><h2 class=\"tabtitle\">Video<\/h2>\n<div class=\"tabcontent\">\n\n<div class=\"nv-iframe-embed\">\n<div class=\"container-lazyload preview-lazyload container-youtube js-lazyload--not-loaded\"><a href=\"https:\/\/www.youtube.com\/watch?v=Nso25TkBsYI\" class=\"lazy-load-youtube preview-lazyload preview-youtube\" data-video-title=\"Python: MergeSort algorithm explained\" title=\"Play video &quot;Python: MergeSort algorithm explained&quot;\">https:\/\/www.youtube.com\/watch?v=Nso25TkBsYI<\/a><noscript>Video can&#8217;t be loaded because JavaScript is disabled: <a href=\"https:\/\/www.youtube.com\/watch?v=Nso25TkBsYI\" title=\"Python: MergeSort algorithm explained\">Python: MergeSort algorithm explained (https:\/\/www.youtube.com\/watch?v=Nso25TkBsYI)<\/a><\/noscript><\/div>\n<\/div>\n<p>&nbsp;<\/p>\n\n<\/div><h2 class=\"tabtitle\">Resources<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Resources<\/h3>\n<p><a href=\"https:\/\/www.aicurriculum.co.uk\/resources\/263217a6-d44a-4cf1-9a5e-4234f87633aa\">Merge sort flashcards, loopcards and quizzes<\/a><\/p>\n<p><a href=\"https:\/\/antoniosarosi.github.io\/Merge-Sort-Visualization\/\">Merge sort interactive animation demo<\/a><\/p>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Merge Sort Time Complexity: O(n log(n)) &#8211; Space Complexity: O(n) Merge Sort is a popular sorting algorithm that follows the\u00a0divide and conquer\u00a0approach. The algorithm works by breaking down the list into smaller sub-lists and sorting them individually. Merge sort steps Divide the unsorted list into smaller sub-lists until each sub-list contains only one element. Repeatedly&hellip;&nbsp;<a href=\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/\" class=\"\" rel=\"bookmark\">Read More &raquo;<span class=\"screen-reader-text\">Merge Sort<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"neve_meta_sidebar":"","neve_meta_container":"","neve_meta_enable_content_width":"off","neve_meta_content_width":100,"neve_meta_title_alignment":"","neve_meta_author_avatar":"","neve_post_elements_order":"","neve_meta_disable_header":"","neve_meta_disable_footer":"","neve_meta_disable_title":""},"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v20.6 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Merge Sort - Edexcel iGCSE Computer Science<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/\" \/>\n<meta property=\"og:locale\" content=\"en_GB\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Merge Sort - Edexcel iGCSE Computer Science\" \/>\n<meta property=\"og:description\" content=\"Merge Sort Time Complexity: O(n log(n)) &#8211; Space Complexity: O(n) Merge Sort is a popular sorting algorithm that follows the\u00a0divide and conquer\u00a0approach. The algorithm works by breaking down the list into smaller sub-lists and sorting them individually. Merge sort steps Divide the unsorted list into smaller sub-lists until each sub-list contains only one element. Repeatedly&hellip;&nbsp;Read More &raquo;Merge Sort\" \/>\n<meta property=\"og:url\" content=\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/\" \/>\n<meta property=\"og:site_name\" content=\"Edexcel iGCSE Computer Science\" \/>\n<meta property=\"article:modified_time\" content=\"2023-11-02T20:24:48+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-content\/uploads\/sites\/27\/2023\/11\/merge-sort-animation.gif\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Estimated reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/\",\"url\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/\",\"name\":\"Merge Sort - Edexcel iGCSE Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/#website\"},\"datePublished\":\"2023-06-09T13:12:28+00:00\",\"dateModified\":\"2023-11-02T20:24:48+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/#breadcrumb\"},\"inLanguage\":\"en-GB\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Merge Sort\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/#website\",\"url\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/\",\"name\":\"Edexcel iGCSE Computer Science\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-GB\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Merge Sort - Edexcel iGCSE Computer Science","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/","og_locale":"en_GB","og_type":"article","og_title":"Merge Sort - Edexcel iGCSE Computer Science","og_description":"Merge Sort Time Complexity: O(n log(n)) &#8211; Space Complexity: O(n) Merge Sort is a popular sorting algorithm that follows the\u00a0divide and conquer\u00a0approach. The algorithm works by breaking down the list into smaller sub-lists and sorting them individually. Merge sort steps Divide the unsorted list into smaller sub-lists until each sub-list contains only one element. Repeatedly&hellip;&nbsp;Read More &raquo;Merge Sort","og_url":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/","og_site_name":"Edexcel iGCSE Computer Science","article_modified_time":"2023-11-02T20:24:48+00:00","og_image":[{"url":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-content\/uploads\/sites\/27\/2023\/11\/merge-sort-animation.gif"}],"twitter_card":"summary_large_image","twitter_misc":{"Estimated reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/","url":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/","name":"Merge Sort - Edexcel iGCSE Computer Science","isPartOf":{"@id":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/#website"},"datePublished":"2023-06-09T13:12:28+00:00","dateModified":"2023-11-02T20:24:48+00:00","breadcrumb":{"@id":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/#breadcrumb"},"inLanguage":"en-GB","potentialAction":[{"@type":"ReadAction","target":["https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/merge-sort\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/"},{"@type":"ListItem","position":2,"name":"Merge Sort"}]},{"@type":"WebSite","@id":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/#website","url":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/","name":"Edexcel iGCSE Computer Science","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-GB"}]}},"rttpg_featured_image_url":null,"rttpg_author":{"display_name":"learnlearnadmin","author_link":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/author\/learnlearnadmin\/"},"rttpg_comment":0,"rttpg_category":null,"rttpg_excerpt":"Merge Sort Time Complexity: O(n log(n)) &#8211; Space Complexity: O(n) Merge Sort is a popular sorting algorithm that follows the\u00a0divide and conquer\u00a0approach. The algorithm works by breaking down the list into smaller sub-lists and sorting them individually. Merge sort steps Divide the unsorted list into smaller sub-lists until each sub-list contains only one element. Repeatedly&hellip;&nbsp;Read&hellip;","_links":{"self":[{"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/pages\/34"}],"collection":[{"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/comments?post=34"}],"version-history":[{"count":6,"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/pages\/34\/revisions"}],"predecessor-version":[{"id":558,"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/pages\/34\/revisions\/558"}],"wp:attachment":[{"href":"https:\/\/learnlearn.uk\/edexcel-igcse-computer-science\/wp-json\/wp\/v2\/media?parent=34"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}