{"id":4071,"date":"2022-01-15T22:07:54","date_gmt":"2022-01-15T14:07:54","guid":{"rendered":"https:\/\/1989lifejourney.com\/?p=4071"},"modified":"2022-01-15T22:08:06","modified_gmt":"2022-01-15T14:08:06","slug":"merge-sort","status":"publish","type":"post","link":"https:\/\/1989lifejourney.com\/?p=4071","title":{"rendered":"Merge sort"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>func merge(arr: inout &#091;Int], front: Int, end: Int, mid: Int) {\n    var arr1 = &#091;Int]()\n    var arr2 = &#091;Int]()\n    for i in front ... mid {\n        arr1.append(arr&#091;i])\n    }\n    for i in (mid + 1) ... end {\n        arr2.append(arr&#091;i])\n    }\n\n    var i = 0\n    var j = 0\n    var k = front\n    while i &lt; arr1.count &amp;&amp; j &lt; arr2.count {\n        if arr1&#091;i] &lt; arr2&#091;j] {\n            arr&#091;k] = arr1&#091;i]\n            i += 1\n            k += 1\n        } else {\n            arr&#091;k] = arr2&#091;j]\n            j += 1\n            k += 1\n        }\n    }\n    \n    while i &lt; arr1.count {\n        arr&#091;k] = arr1&#091;i]\n        i += 1\n        k += 1\n    }\n    \n    while j &lt; arr2.count {\n        arr&#091;k] = arr2&#091;j]\n        j += 1\n        k += 1\n    }\n}\n\nfunc mergeSort(arr: inout &#091;Int], front: Int, end: Int) {\n    if front &lt; end {\n        let mid = (front + end) \/ 2\n        mergeSort(arr: &amp;arr, front: front, end: mid)\n        mergeSort(arr: &amp;arr, front: mid + 1, end: end)\n        merge(arr: &amp;arr, front: front, end: end, mid: mid)\n    }\n}\n\nvar arr = &#091;6, 5, 4, 3, 2, 1]\nmergeSort(arr: &amp;arr, front: 0, end: arr.count - 1)\nprint(arr)<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"time-complexity\"><strong>Time complexity:<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Best case: O(nlogn)<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Average case: O(nlogn)<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Worst case: O(nlogn)<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Ref:<\/strong> <a href=\"https:\/\/www.geeksforgeeks.org\/merge-sort\/\">https:\/\/www.geeksforgeeks.org\/merge-sort\/<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Ref:<\/strong> <a href=\"http:\/\/alrightchiu.github.io\/SecondRound\/comparison-sort-merge-sorthe-bing-pai-xu-fa.html\">http:\/\/alrightchiu.github.io\/SecondRound\/comparison-sort-merge-sorthe-bing-pai-xu-fa.html<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Time complexity: Best case: O(nlogn) Average case: O(nl [&hellip;]<\/p>\n","protected":false},"author":139426785,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_coblocks_attr":"","_coblocks_dimensions":"","_coblocks_responsive_height":"","_coblocks_accordion_ie_support":"","_postgate_lock_override":"inherit","_postgate_lock_mode":"inherit","_postgate_preview_mode":"inherit","_postgate_preview_limit":0,"_postgate_product_ids":[],"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":true,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_wpcom_ai_launchpad_first_post":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[37324612,1],"tags":[],"post_folder":[],"class_list":["post-4071","post","type-post","status-publish","format-standard","hentry","category-ios-development","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/paR5vw-13F","jetpack-related-posts":[{"id":4067,"url":"https:\/\/1989lifejourney.com\/?p=4067","url_meta":{"origin":4071,"position":0},"title":"Quick Sort","author":"Kevin","date":"15 1 \u6708, 2022","format":false,"excerpt":"func partition(arr: inout [Int], front: Int, \u2026","rel":"","context":"\u5728\u300cIOS Development\u300d\u4e2d","block_context":{"text":"IOS Development","link":"https:\/\/1989lifejourney.com\/?cat=37324612"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":4604,"url":"https:\/\/1989lifejourney.com\/?p=4604","url_meta":{"origin":4071,"position":1},"title":"Print all permutation of an array","author":"Kevin","date":"26 2 \u6708, 2022","format":false,"excerpt":"\u984c\u76ee: \u7d66\u5b9a\u4e00\u7d44\u6574\u6578array\uff0c\u5370\u51fa\u6240\u6709\u7684\u6392\u5217\u7d44\u5408 EX: input: [1,2], output\u2026","rel":"","context":"\u5728\u300cLeetCode\u300d\u4e2d","block_context":{"text":"LeetCode","link":"https:\/\/1989lifejourney.com\/?cat=89600350"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":4134,"url":"https:\/\/1989lifejourney.com\/?p=4134","url_meta":{"origin":4071,"position":2},"title":"System Design Practice &#8211; 1","author":"Kevin","date":"30 1 \u6708, 2022","format":false,"excerpt":"\u984c\u76ee: \u67093\u7a2eRoutine:(1)\u6bcf\u500bRoutine\u6709\u76f8\u540c\u7684\u5c6c\u6027\uff0c\u4f46\u4e5f\u6709\u5404\u5225\u4e0d\u540c\u7684\u5c6c\u6027(2)\u6bcf\u500bR\u2026","rel":"","context":"\u5728\u300cIOS Development\u300d\u4e2d","block_context":{"text":"IOS Development","link":"https:\/\/1989lifejourney.com\/?cat=37324612"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":4982,"url":"https:\/\/1989lifejourney.com\/?p=4982","url_meta":{"origin":4071,"position":3},"title":"Difference between value type and a reference type in iOS swift\ufffc","author":"Kevin","date":"29 3 \u6708, 2022","format":false,"excerpt":"\u4ee5\u4e0b\u8cc7\u6599\u7686\u53c3\u8003\u81eaRef1\uff0c\u9019\u88e1\u50c5\u4f5c\u500b\u4eba\u5b78\u7fd2\u6574\u7406: Definition of Value type \u2026","rel":"","context":"\u5728\u300cIOS Development\u300d\u4e2d","block_context":{"text":"IOS Development","link":"https:\/\/1989lifejourney.com\/?cat=37324612"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":4099,"url":"https:\/\/1989lifejourney.com\/?p=4099","url_meta":{"origin":4071,"position":4},"title":"\u8e29\u5730\u96f7\u7a0b\u5f0f Swift Code","author":"Kevin","date":"25 1 \u6708, 2022","format":false,"excerpt":"\u7d66\u5b9a\u5217\u6578(row)\u548c\u884c\u6578(col)\u4ee5\u53ca\u5168\u90e8\u7684\u5730\u96f7\u500b\u6578\uff0c\u5beb\u51fa\u8e29\u5730\u96f7\u904a\u6232 \/\/ -1 represent\u2026","rel":"","context":"\u5728\u300cIOS Development\u300d\u4e2d","block_context":{"text":"IOS Development","link":"https:\/\/1989lifejourney.com\/?cat=37324612"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":4857,"url":"https:\/\/1989lifejourney.com\/?p=4857","url_meta":{"origin":4071,"position":5},"title":"Array Permutation\/Combination by Iterative","author":"Kevin","date":"21 3 \u6708, 2022","format":false,"excerpt":"\u53c3\u8003\u5be6\u4f5c: https:\/\/www.youtube.com\/watch?v=zIY2BWdsbFs \u2026","rel":"","context":"\u5728\u300cLeetCode\u300d\u4e2d","block_context":{"text":"LeetCode","link":"https:\/\/1989lifejourney.com\/?cat=89600350"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts\/4071","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/users\/139426785"}],"replies":[{"embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4071"}],"version-history":[{"count":2,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts\/4071\/revisions"}],"predecessor-version":[{"id":4073,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts\/4071\/revisions\/4073"}],"wp:attachment":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4071"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4071"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4071"},{"taxonomy":"post_folder","embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fpost_folder&post=4071"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}