{"id":34198,"date":"2024-11-01T09:25:25","date_gmt":"2024-11-01T09:25:25","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34198"},"modified":"2024-11-01T10:58:12","modified_gmt":"2024-11-01T10:58:12","slug":"c-coding-test-course-merge-sort-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34198\/","title":{"rendered":"C++ Coding Test Course, Merge Sort"},"content":{"rendered":"
\n

1. Problem Description<\/h2>\n

\n This is a problem to sort a given list of integers in ascending order. It is solved using the
\n Merge Sort<\/em> algorithm. Merge sort is a type of divide and conquer algorithm that recursively divides the given list into two sub-lists, sorts each of them, and then merges them back into a single list.\n <\/p>\n

2. Problem Input<\/h2>\n

\n – The first input is the number of integers to be sorted N<\/code> (1 \u2264 N<\/code> \u2264 106<\/sup>).
\n – The second input consists of N<\/code> integers. These integers may include any negative and
\n positive values, and each integer is within the range of 32-bit integers.\n <\/p>\n

3. Problem Output<\/h2>\n

\n Output the sorted integer list, with each integer separated by a space.\n <\/p>\n

4. Algorithm Description<\/h2>\n

\n The main idea of merge sort is to divide the array into two parts at the midpoint, recursively sort each part, and then merge the two sorted parts to create the final sorted array.\n <\/p>\n

4.1 Algorithm Steps<\/h3>\n
    \n
  1. If the size of the array is 1 or less, it is already sorted, so return that array.<\/li>\n
  2. Split the array into two sub-arrays based on the midpoint index.<\/li>\n
  3. Recursively call merge sort on each sub-array.<\/li>\n
  4. Merge the two sorted sub-arrays to form one sorted array.<\/li>\n<\/ol>\n

    5. Code Implementation<\/h2>\n
    \n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\n\/\/ Function to merge two arrays\nvoid merge(vector &arr, int left, int mid, int right) {\n    int n1 = mid - left + 1; \/\/ Size of left array\n    int n2 = right - mid;    \/\/ Size of right array\n    vector L(n1), R(n2); \/\/ Create sub-arrays\n\n    \/\/ Store values in sub-arrays\n    for (int i = 0; i < n1; ++i)\n        L[i] = arr[left + i];\n    for (int j = 0; j < n2; ++j)\n        R[j] = arr[mid + 1 + j];\n\n    \/\/ Merge sub-arrays\n    int i = 0; \/\/ Index i for L\n    int j = 0; \/\/ Index j for R\n    int k = left; \/\/ Index k for arr\n\n    while (i < n1 && j < n2) {\n        if (L[i] <= R[j]) {\n            arr[k] = L[i];\n            i++;\n        } else {\n            arr[k] = R[j];\n            j++;\n        }\n        k++;\n    }\n\n    \/\/ Process remaining elements\n    while (i < n1) {\n        arr[k] = L[i];\n        i++;\n        k++;\n    }\n    while (j < n2) {\n        arr[k] = R[j];\n        j++;\n        k++;\n    }\n}\n\n\/\/ Merge sort function\nvoid mergeSort(vector &arr, int left, int right) {\n    if (left < right) {\n        int mid = left + (right - left) \/ 2; \/\/ Calculate midpoint\n\n        mergeSort(arr, left, mid); \/\/ Sort left array\n        mergeSort(arr, mid + 1, right); \/\/ Sort right array\n\n        merge(arr, left, mid, right); \/\/ Merge two arrays\n    }\n}\n\nint main() {\n    int N;\n    cin >> N; \/\/ Input number of integers\n    vector arr(N);\n\n    for (int i = 0; i < N; i++) {\n        cin >> arr[i]; \/\/ Input integer list\n    }\n\n    mergeSort(arr, 0, N - 1); \/\/ Call merge sort\n\n    \/\/ Output result\n    for (int i = 0; i < N; i++) {\n        cout << arr[i];\n        if (i < N - 1) cout << \" \"; \/\/ Space separation\n    }\n    cout << endl;\n\n    return 0;\n}\n    <\/int><\/int><\/int><\/int><\/code><\/pre>\n
    6. Complexity Analysis<\/h2>\n
    \n        The time complexity of merge sort is O(N log N)<\/code>, where N<\/code> is the size of the array.
    \n        This is due to the depth of log N<\/code> from the array being divided in half,
    \n        and N<\/code> time required to merge at each level.
    \n        Therefore, merge sort guarantees O(N log N)<\/code> performance in both average and worst-case scenarios.\n    <\/p>\n
    \n        The space complexity relates to the additional memory used,
    \n        as merge sort generates two sub-arrays, requiring O(N)<\/code> additional memory.\n    <\/p>\n
    7. Conclusion<\/h2>\n
    \n        The merge sort algorithm is stable and effective for sorting large amounts of data.
    \n        It can be utilized in various programming tasks and problem-solving scenarios.
    \n        Unlike ultra-fast sorting algorithms (e.g., Quick Sort),
    \n        merge sort is characterized by consistent performance and simple implementation, making it popular in many situations.\n    <\/p>\n
    8. Additional Practice Problems<\/h2>\n
    \n        Please solve the following problems.\n    <\/p>\n
      \n
    1. Write a program to find the mode in a given list.<\/li>\n
    2. Write a program using merge sort to merge two sorted arrays into one sorted array.<\/li>\n<\/ol>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
      1. Problem Description This is a problem to sort a given list of integers in ascending order. It is solved using the Merge Sort algorithm. Merge sort is a type of divide and conquer algorithm that recursively divides the given list into two sub-lists, sorts each of them, and then merges them back into a … \ub354 \ubcf4\uae30 “C++ Coding Test Course, Merge Sort”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[111],"tags":[],"class_list":["post-34198","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials-2"],"yoast_head":"\nC++ Coding Test Course, Merge Sort - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/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:\/\/atmokpo.com\/w\/34198\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C++ Coding Test Course, Merge Sort - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"1. Problem Description This is a problem to sort a given list of integers in ascending order. It is solved using the Merge Sort algorithm. Merge sort is a type of divide and conquer algorithm that recursively divides the given list into two sub-lists, sorts each of them, and then merges them back into a … \ub354 \ubcf4\uae30 "C++ Coding Test Course, Merge Sort"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34198\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:25:25+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:58:12+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34198\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34198\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C++ Coding Test Course, Merge Sort\",\"datePublished\":\"2024-11-01T09:25:25+00:00\",\"dateModified\":\"2024-11-01T10:58:12+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34198\/\"},\"wordCount\":352,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C++ Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34198\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34198\/\",\"name\":\"C++ Coding Test Course, Merge Sort - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:25:25+00:00\",\"dateModified\":\"2024-11-01T10:58:12+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34198\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34198\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34198\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C++ Coding Test Course, Merge Sort\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C++ Coding Test Course, Merge Sort - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","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:\/\/atmokpo.com\/w\/34198\/","og_locale":"ko_KR","og_type":"article","og_title":"C++ Coding Test Course, Merge Sort - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"1. Problem Description This is a problem to sort a given list of integers in ascending order. It is solved using the Merge Sort algorithm. Merge sort is a type of divide and conquer algorithm that recursively divides the given list into two sub-lists, sorts each of them, and then merges them back into a … \ub354 \ubcf4\uae30 \"C++ Coding Test Course, Merge Sort\"","og_url":"https:\/\/atmokpo.com\/w\/34198\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:25:25+00:00","article_modified_time":"2024-11-01T10:58:12+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34198\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34198\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C++ Coding Test Course, Merge Sort","datePublished":"2024-11-01T09:25:25+00:00","dateModified":"2024-11-01T10:58:12+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34198\/"},"wordCount":352,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C++ Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34198\/","url":"https:\/\/atmokpo.com\/w\/34198\/","name":"C++ Coding Test Course, Merge Sort - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:25:25+00:00","dateModified":"2024-11-01T10:58:12+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34198\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34198\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34198\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C++ Coding Test Course, Merge Sort"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34198","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34198"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34198\/revisions"}],"predecessor-version":[{"id":34199,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34198\/revisions\/34199"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34198"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34198"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34198"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}