CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="ja" dir="ltr"> <head> <meta charset="UTF-8"> <title>マージソート - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )jawikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"ja", "wgMonthNames":["","1月","2月","3月","4月","5月","6月","7月","8月","9月","10月","11月","12月"],"wgRequestId":"d41a2ea4-7273-4c22-bfe2-95bf4eec50e8","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"マージソート","wgTitle":"マージソート","wgCurRevisionId":89273506,"wgRevisionId":89273506,"wgArticleId":12759,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["ソート"],"wgPageViewLanguage":"ja","wgPageContentLanguage":"ja","wgPageContentModel":"wikitext","wgRelevantPageName":"マージソート","wgRelevantArticleId":12759,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"ja","pageLanguageDir":"ltr", "pageVariantFallbacks":"ja"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":10000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q189057","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.gadget.PDFLinkIcon":"ready","ext.gadget.RedirectColor":"ready","ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options": "loading","ext.math.styles":"ready","ext.cite.styles":"ready","ext.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.NormalizeCharWidth","ext.gadget.suppressEnterAtSummaryBox","ext.gadget.checkSignature","ext.gadget.charinsert","ext.gadget.WikiMiniAtlas","ext.gadget.switcher","ext.gadget.protectionIndicator","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init", "ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=ja&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=ja&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=ja&modules=ext.gadget.PDFLinkIcon%2CRedirectColor&only=styles&skin=vector-2022"> <link rel="stylesheet" href="/w/load.php?lang=ja&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="720"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="480"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="384"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="マージソート - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//ja.m.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88"> <link rel="alternate" type="application/x-wiki" title="編集" href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (ja)"> <link rel="EditURI" type="application/rsd+xml" href="//ja.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.ja"> <link rel="alternate" type="application/atom+xml" title="WikipediaのAtomフィード" href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E6%9C%80%E8%BF%91%E3%81%AE%E6%9B%B4%E6%96%B0&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-マージソート rootpage-マージソート skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">コンテンツにスキップ</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="サイト"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="メインメニュー" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > メインメニュー </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">メインメニュー</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">サイドバーに移動</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">非表示</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> 案内 </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/%E3%83%A1%E3%82%A4%E3%83%B3%E3%83%9A%E3%83%BC%E3%82%B8" title="メインページに移動する [z]" accesskey="z">メインページ</a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:%E3%82%B3%E3%83%9F%E3%83%A5%E3%83%8B%E3%83%86%E3%82%A3%E3%83%BB%E3%83%9D%E3%83%BC%E3%82%BF%E3%83%AB" title="このプロジェクトについて、できること、情報を入手する場所">コミュニティ・ポータル</a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:%E6%9C%80%E8%BF%91%E3%81%AE%E5%87%BA%E6%9D%A5%E4%BA%8B" title="最近の出来事の背景を知る">最近の出来事</a></li><li id="n-newpages" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E6%96%B0%E3%81%97%E3%81%84%E3%83%9A%E3%83%BC%E3%82%B8" title="最近新規に作成されたページの一覧">新しいページ</a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E6%9C%80%E8%BF%91%E3%81%AE%E6%9B%B4%E6%96%B0" title="このウィキにおける最近の更新の一覧 [r]" accesskey="r">最近の更新</a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E3%81%8A%E3%81%BE%E3%81%8B%E3%81%9B%E8%A1%A8%E7%A4%BA" title="無作為に選択されたページを読み込む [x]" accesskey="x">おまかせ表示</a></li><li id="n-sandbox" class="mw-list-item"><a href="/wiki/Wikipedia:%E3%82%B5%E3%83%B3%E3%83%89%E3%83%9C%E3%83%83%E3%82%AF%E3%82%B9" title="練習用のページ">練習用ページ</a></li><li id="n-commonsupload" class="mw-list-item"><a href="//commons.wikimedia.org/wiki/Special:UploadWizard?uselang=ja" title="画像やメディアファイルをウィキメディア・コモンズにアップロード">アップロード (ウィキメディア・コモンズ)</a></li> </ul> </div> </div> <div id="p-help" class="vector-menu mw-portlet mw-portlet-help" > <div class="vector-menu-heading"> ヘルプ </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:%E7%9B%AE%E6%AC%A1" title="情報を得る場所">ヘルプ</a></li><li id="n-villagepump" class="mw-list-item"><a href="/wiki/Wikipedia:%E4%BA%95%E6%88%B8%E7%AB%AF" title="プロジェクトについての意見交換">井戸端</a></li><li id="n-notice" class="mw-list-item"><a href="/wiki/Wikipedia:%E3%81%8A%E7%9F%A5%E3%82%89%E3%81%9B" title="プロジェクトについてのお知らせ">お知らせ</a></li><li id="n-bugreportspage" class="mw-list-item"><a href="/wiki/Wikipedia:%E3%83%90%E3%82%B0%E3%81%AE%E5%A0%B1%E5%91%8A" title="ウィキペディア・ソフトウェアのバグ報告">バグの報告</a></li><li id="n-contact" class="mw-list-item"><a href="/wiki/Wikipedia:%E9%80%A3%E7%B5%A1%E5%85%88" title="ウィキペディアやウィキメディア財団に関する連絡先">ウィキペディアに関するお問い合わせ</a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/%E3%83%A1%E3%82%A4%E3%83%B3%E3%83%9A%E3%83%BC%E3%82%B8" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-ja.svg" style="width: 7.5em; height: 1.25em;"> <img class="mw-logo-tagline" alt="" src="/static/images/mobile/copyright/wikipedia-tagline-ja.svg" width="100" height="14" style="width: 6.25em; height: 0.875em;"> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/%E7%89%B9%E5%88%A5:%E6%A4%9C%E7%B4%A2" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Wikipedia内を検索 [f]" accesskey="f"> 検索 </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Wikipedia内を検索" aria-label="Wikipedia内を検索" autocapitalize="sentences" title="Wikipedia内を検索 [f]" accesskey="f" id="searchInput" > </div> <input type="hidden" name="title" value="特別:検索"> </div> <button class="cdx-button cdx-search-input__end-button">検索</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="個人用ツール"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="表示"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="ページのフォントサイズ、幅、色の外観を変更する" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="表示" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > 表示 </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_ja.wikipedia.org&uselang=ja" class="">寄付</a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%82%A2%E3%82%AB%E3%82%A6%E3%83%B3%E3%83%88%E4%BD%9C%E6%88%90&returnto=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88" title="アカウントを作成してログインすることをお勧めしますが、必須ではありません" class="">アカウント作成</a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%83%AD%E3%82%B0%E3%82%A4%E3%83%B3&returnto=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88" title="ログインすることを推奨します。ただし、必須ではありません。 [o]" accesskey="o" class="">ログイン</a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="その他の操作" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="個人用ツール" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > 個人用ツール </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="利用者メニュー" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_ja.wikipedia.org&uselang=ja">寄付</a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%82%A2%E3%82%AB%E3%82%A6%E3%83%B3%E3%83%88%E4%BD%9C%E6%88%90&returnto=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88" title="アカウントを作成してログインすることをお勧めしますが、必須ではありません"> アカウント作成</a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%83%AD%E3%82%B0%E3%82%A4%E3%83%B3&returnto=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88" title="ログインすることを推奨します。ただし、必須ではありません。 [o]" accesskey="o"> ログイン</a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> ログアウトした編集者のページ <a href="/wiki/Wikipedia:%E3%82%A6%E3%82%A3%E3%82%AD%E3%83%9A%E3%83%87%E3%82%A3%E3%82%A2%E3%81%B8%E3%82%88%E3%81%86%E3%81%93%E3%81%9D" aria-label="編集の詳細">もっと詳しく</a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E8%87%AA%E5%88%86%E3%81%AE%E6%8A%95%E7%A8%BF%E8%A8%98%E9%8C%B2" title="このIPアドレスからなされた編集の一覧 [y]" accesskey="y">投稿記録</a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E3%83%88%E3%83%BC%E3%82%AF%E3%83%9A%E3%83%BC%E3%82%B8" title="このIPアドレスからなされた編集についての議論 [n]" accesskey="n">トーク</a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="サイト"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="目次" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">目次</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">サイドバーに移動</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">非表示</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">ページ先頭</div> </a> </li> <li id="toc-アルゴリズム" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#アルゴリズム"> <div class="vector-toc-text"> 1 アルゴリズム </div> </a> <button aria-controls="toc-アルゴリズム-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> アルゴリズムサブセクションを切り替えます </button> <ul id="toc-アルゴリズム-sublist" class="vector-toc-list"> <li id="toc-実装例" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#実装例"> <div class="vector-toc-text"> 1.1 実装例 </div> </a> <ul id="toc-実装例-sublist" class="vector-toc-list"> <li id="toc-C" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#C"> <div class="vector-toc-text"> 1.1.1 C </div> </a> <ul id="toc-C-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Ruby" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Ruby"> <div class="vector-toc-text"> 1.1.2 Ruby </div> </a> <ul id="toc-Ruby-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Haskell" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Haskell"> <div class="vector-toc-text"> 1.1.3 Haskell </div> </a> <ul id="toc-Haskell-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Scheme" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Scheme"> <div class="vector-toc-text"> 1.1.4 Scheme </div> </a> <ul id="toc-Scheme-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-アルゴリズムの動作例" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#アルゴリズムの動作例"> <div class="vector-toc-text"> 2 アルゴリズムの動作例 </div> </a> <ul id="toc-アルゴリズムの動作例-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-脚注" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#脚注"> <div class="vector-toc-text"> 3 脚注 </div> </a> <ul id="toc-脚注-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-関連項目" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#関連項目"> <div class="vector-toc-text"> 4 関連項目 </div> </a> <ul id="toc-関連項目-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-外部リンク" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#外部リンク"> <div class="vector-toc-text"> 5 外部リンク </div> </a> <ul id="toc-外部リンク-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="目次" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="目次の表示・非表示を切り替え" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > 目次の表示・非表示を切り替え </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading">マージソート</h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="特定の記事の別の言語版に移動します。利用可能な言語47件" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-47" aria-hidden="true" > 47の言語版 </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%AA%D8%B5%D9%86%D9%8A%D9%81_%D8%AF%D9%85%D8%AC%D9%8A" title="アラビア語: تصنيف دمجي" lang="ar" hreflang="ar" data-title="تصنيف دمجي" data-language-autonym="العربية" data-language-local-name="アラビア語" class="interlanguage-link-target">العربية</a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/Birl%C9%99%C5%9Fdirm%C9%99li_nizamlama" title="アゼルバイジャン語: Birləşdirməli nizamlama" lang="az" hreflang="az" data-title="Birləşdirməli nizamlama" data-language-autonym="Azərbaycanca" data-language-local-name="アゼルバイジャン語" class="interlanguage-link-target">Azərbaycanca</a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%B0%D0%BD%D0%B5_%D1%87%D1%80%D0%B5%D0%B7_%D1%81%D0%BB%D0%B8%D0%B2%D0%B0%D0%BD%D0%B5" title="ブルガリア語: Сортиране чрез сливане" lang="bg" hreflang="bg" data-title="Сортиране чрез сливане" data-language-autonym="Български" data-language-local-name="ブルガリア語" class="interlanguage-link-target">Български</a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/%C5%98azen%C3%AD_slu%C4%8Dov%C3%A1n%C3%ADm" title="チェコ語: Řazení slučováním" lang="cs" hreflang="cs" data-title="Řazení slučováním" data-language-autonym="Čeština" data-language-local-name="チェコ語" class="interlanguage-link-target">Čeština</a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Flettesortering" title="デンマーク語: Flettesortering" lang="da" hreflang="da" data-title="Flettesortering" data-language-autonym="Dansk" data-language-local-name="デンマーク語" class="interlanguage-link-target">Dansk</a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Mergesort" title="ドイツ語: Mergesort" lang="de" hreflang="de" data-title="Mergesort" data-language-autonym="Deutsch" data-language-local-name="ドイツ語" class="interlanguage-link-target">Deutsch</a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%A4%CE%B1%CE%BE%CE%B9%CE%BD%CF%8C%CE%BC%CE%B7%CF%83%CE%B7_%CE%BC%CE%B5_%CF%83%CF%85%CE%B3%CF%87%CF%8E%CE%BD%CE%B5%CF%85%CF%83%CE%B7" title="ギリシャ語: Ταξινόμηση με συγχώνευση" lang="el" hreflang="el" data-title="Ταξινόμηση με συγχώνευση" data-language-autonym="Ελληνικά" data-language-local-name="ギリシャ語" class="interlanguage-link-target">Ελληνικά</a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Merge_sort" title="英語: Merge sort" lang="en" hreflang="en" data-title="Merge sort" data-language-autonym="English" data-language-local-name="英語" class="interlanguage-link-target">English</a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Kunfanda_ordigo" title="エスペラント語: Kunfanda ordigo" lang="eo" hreflang="eo" data-title="Kunfanda ordigo" data-language-autonym="Esperanto" data-language-local-name="エスペラント語" class="interlanguage-link-target">Esperanto</a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Ordenamiento_por_mezcla" title="スペイン語: Ordenamiento por mezcla" lang="es" hreflang="es" data-title="Ordenamiento por mezcla" data-language-autonym="Español" data-language-local-name="スペイン語" class="interlanguage-link-target">Español</a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Mestimissortimine" title="エストニア語: Mestimissortimine" lang="et" hreflang="et" data-title="Mestimissortimine" data-language-autonym="Eesti" data-language-local-name="エストニア語" class="interlanguage-link-target">Eesti</a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%85%D8%B1%D8%AA%D8%A8%E2%80%8C%D8%B3%D8%A7%D8%B2%DB%8C_%D8%A7%D8%AF%D8%BA%D8%A7%D9%85%DB%8C" title="ペルシア語: مرتب‌سازی ادغامی" lang="fa" hreflang="fa" data-title="مرتب‌سازی ادغامی" data-language-autonym="فارسی" data-language-local-name="ペルシア語" class="interlanguage-link-target">فارسی</a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Lomituslajittelu" title="フィンランド語: Lomituslajittelu" lang="fi" hreflang="fi" data-title="Lomituslajittelu" data-language-autonym="Suomi" data-language-local-name="フィンランド語" class="interlanguage-link-target">Suomi</a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Tri_fusion" title="フランス語: Tri fusion" lang="fr" hreflang="fr" data-title="Tri fusion" data-language-autonym="Français" data-language-local-name="フランス語" class="interlanguage-link-target">Français</a></li><li class="interlanguage-link interwiki-ga mw-list-item"><a href="https://ga.wikipedia.org/wiki/Sort%C3%A1il_is_cumaisc" title="アイルランド語: Sortáil is cumaisc" lang="ga" hreflang="ga" data-title="Sortáil is cumaisc" data-language-autonym="Gaeilge" data-language-local-name="アイルランド語" class="interlanguage-link-target">Gaeilge</a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%9E%D7%99%D7%95%D7%9F_%D7%9E%D7%99%D7%96%D7%95%D7%92" title="ヘブライ語: מיון מיזוג" lang="he" hreflang="he" data-title="מיון מיזוג" data-language-autonym="עברית" data-language-local-name="ヘブライ語" class="interlanguage-link-target">עברית</a></li><li class="interlanguage-link interwiki-hi mw-list-item"><a href="https://hi.wikipedia.org/wiki/%E0%A4%AE%E0%A4%B0%E0%A5%8D%E0%A4%9C_%E0%A4%B8%E0%A5%89%E0%A4%B0%E0%A5%8D%E0%A4%9F" title="ヒンディー語: मर्ज सॉर्ट" lang="hi" hreflang="hi" data-title="मर्ज सॉर्ट" data-language-autonym="हिन्दी" data-language-local-name="ヒンディー語" class="interlanguage-link-target">हिन्दी</a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/%C3%96sszef%C3%A9s%C3%BCl%C3%A9ses_rendez%C3%A9s" title="ハンガリー語: Összefésüléses rendezés" lang="hu" hreflang="hu" data-title="Összefésüléses rendezés" data-language-autonym="Magyar" data-language-local-name="ハンガリー語" class="interlanguage-link-target">Magyar</a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D5%84%D5%AB%D5%A1%D5%B1%D5%B8%D6%82%D5%AC%D5%B4%D5%A1%D5%B6_%D5%BF%D5%A5%D5%BD%D5%A1%D5%AF%D5%A1%D5%BE%D5%B8%D6%80%D5%B8%D6%82%D5%B4" title="アルメニア語: Միաձուլման տեսակավորում" lang="hy" hreflang="hy" data-title="Միաձուլման տեսակավորում" data-language-autonym="Հայերեն" data-language-local-name="アルメニア語" class="interlanguage-link-target">Հայերեն</a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Urut_gabung" title="インドネシア語: Urut gabung" lang="id" hreflang="id" data-title="Urut gabung" data-language-autonym="Bahasa Indonesia" data-language-local-name="インドネシア語" class="interlanguage-link-target">Bahasa Indonesia</a></li><li class="interlanguage-link interwiki-is mw-list-item"><a href="https://is.wikipedia.org/wiki/Sameiningarr%C3%B6%C3%B0un" title="アイスランド語: Sameiningarröðun" lang="is" hreflang="is" data-title="Sameiningarröðun" data-language-autonym="Íslenska" data-language-local-name="アイスランド語" class="interlanguage-link-target">Íslenska</a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Merge_sort" title="イタリア語: Merge sort" lang="it" hreflang="it" data-title="Merge sort" data-language-autonym="Italiano" data-language-local-name="イタリア語" class="interlanguage-link-target">Italiano</a></li><li class="interlanguage-link interwiki-kk mw-list-item"><a href="https://kk.wikipedia.org/wiki/%D0%A2%D0%BE%D2%93%D1%8B%D1%81%D1%82%D1%8B%D1%80%D1%83_%D0%B0%D1%80%D2%9B%D1%8B%D0%BB%D1%8B_%D1%81%D2%B1%D1%80%D1%8B%D0%BF%D1%82%D0%B0%D1%83" title="カザフ語: Тоғыстыру арқылы сұрыптау" lang="kk" hreflang="kk" data-title="Тоғыстыру арқылы сұрыптау" data-language-autonym="Қазақша" data-language-local-name="カザフ語" class="interlanguage-link-target">Қазақша</a></li><li class="interlanguage-link interwiki-kn mw-list-item"><a href="https://kn.wikipedia.org/wiki/%E0%B2%AE%E0%B2%B0%E0%B3%8D%E0%B2%9C%E0%B3%8D_%E0%B2%B8%E0%B2%BE%E0%B2%B0%E0%B3%8D%E0%B2%9F%E0%B3%8D_(%E0%B2%B5%E0%B2%BF%E0%B2%B2%E0%B3%80%E0%B2%A8_%E0%B2%B5%E0%B2%BF%E0%B2%82%E0%B2%97%E0%B2%A1%E0%B2%A3%E0%B3%86)" title="カンナダ語: ಮರ್ಜ್ ಸಾರ್ಟ್ (ವಿಲೀನ ವಿಂಗಡಣೆ)" lang="kn" hreflang="kn" data-title="ಮರ್ಜ್ ಸಾರ್ಟ್ (ವಿಲೀನ ವಿಂಗಡಣೆ)" data-language-autonym="ಕನ್ನಡ" data-language-local-name="カンナダ語" class="interlanguage-link-target">ಕನ್ನಡ</a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC" title="韓国語: 합병 정렬" lang="ko" hreflang="ko" data-title="합병 정렬" data-language-autonym="한국어" data-language-local-name="韓国語" class="interlanguage-link-target">한국어</a></li><li class="interlanguage-link interwiki-lb mw-list-item"><a href="https://lb.wikipedia.org/wiki/Mergesort" title="ルクセンブルク語: Mergesort" lang="lb" hreflang="lb" data-title="Mergesort" data-language-autonym="Lëtzebuergesch" data-language-local-name="ルクセンブルク語" class="interlanguage-link-target">Lëtzebuergesch</a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/Merge_Sort" title="ロンバルド語: Merge Sort" lang="lmo" hreflang="lmo" data-title="Merge Sort" data-language-autonym="Lombard" data-language-local-name="ロンバルド語" class="interlanguage-link-target">Lombard</a></li><li class="interlanguage-link interwiki-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/S%C4%85lajinis_rikiavimas" title="リトアニア語: Sąlajinis rikiavimas" lang="lt" hreflang="lt" data-title="Sąlajinis rikiavimas" data-language-autonym="Lietuvių" data-language-local-name="リトアニア語" class="interlanguage-link-target">Lietuvių</a></li><li class="interlanguage-link interwiki-ml mw-list-item"><a href="https://ml.wikipedia.org/wiki/%E0%B4%AE%E0%B5%86%E0%B5%BC%E0%B4%9C%E0%B5%8D_%E0%B4%B8%E0%B5%8B%E0%B5%BC%E0%B4%9F%E0%B5%8D%E0%B4%9F%E0%B5%8D" title="マラヤーラム語: മെർജ് സോർട്ട്" lang="ml" hreflang="ml" data-title="മെർജ് സോർട്ട്" data-language-autonym="മലയാളം" data-language-local-name="マラヤーラム語" class="interlanguage-link-target">മലയാളം</a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Mergesort" title="オランダ語: Mergesort" lang="nl" hreflang="nl" data-title="Mergesort" data-language-autonym="Nederlands" data-language-local-name="オランダ語" class="interlanguage-link-target">Nederlands</a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Sorteringsalgoritme#Flettesortering" title="ノルウェー語(ブークモール): Sorteringsalgoritme" lang="nb" hreflang="nb" data-title="Sorteringsalgoritme" data-language-autonym="Norsk bokmål" data-language-local-name="ノルウェー語(ブークモール)" class="interlanguage-link-target">Norsk bokmål</a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Sortowanie_przez_scalanie" title="ポーランド語: Sortowanie przez scalanie" lang="pl" hreflang="pl" data-title="Sortowanie przez scalanie" data-language-autonym="Polski" data-language-local-name="ポーランド語" class="interlanguage-link-target">Polski</a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Merge_sort" title="ポルトガル語: Merge sort" lang="pt" hreflang="pt" data-title="Merge sort" data-language-autonym="Português" data-language-local-name="ポルトガル語" class="interlanguage-link-target">Português</a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Merge_sort" title="ルーマニア語: Merge sort" lang="ro" hreflang="ro" data-title="Merge sort" data-language-autonym="Română" data-language-local-name="ルーマニア語" class="interlanguage-link-target">Română</a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC" title="ロシア語: Сортировка слиянием" lang="ru" hreflang="ru" data-title="Сортировка слиянием" data-language-autonym="Русский" data-language-local-name="ロシア語" class="interlanguage-link-target">Русский</a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Merge_sort" title="シンプル英語: Merge sort" lang="en-simple" hreflang="en-simple" data-title="Merge sort" data-language-autonym="Simple English" data-language-local-name="シンプル英語" class="interlanguage-link-target">Simple English</a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Triedenie_zlu%C4%8Dovan%C3%ADm" title="スロバキア語: Triedenie zlučovaním" lang="sk" hreflang="sk" data-title="Triedenie zlučovaním" data-language-autonym="Slovenčina" data-language-local-name="スロバキア語" class="interlanguage-link-target">Slovenčina</a></li><li class="interlanguage-link interwiki-sl mw-list-item"><a href="https://sl.wikipedia.org/wiki/Urejanje_z_zlivanjem" title="スロベニア語: Urejanje z zlivanjem" lang="sl" hreflang="sl" data-title="Urejanje z zlivanjem" data-language-autonym="Slovenščina" data-language-local-name="スロベニア語" class="interlanguage-link-target">Slovenščina</a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Sortiranje_spajanjem" title="セルビア語: Sortiranje spajanjem" lang="sr" hreflang="sr" data-title="Sortiranje spajanjem" data-language-autonym="Српски / srpski" data-language-local-name="セルビア語" class="interlanguage-link-target">Српски / srpski</a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Merge_sort" title="スウェーデン語: Merge sort" lang="sv" hreflang="sv" data-title="Merge sort" data-language-autonym="Svenska" data-language-local-name="スウェーデン語" class="interlanguage-link-target">Svenska</a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B9%80%E0%B8%A3%E0%B8%B5%E0%B8%A2%E0%B8%87%E0%B8%A5%E0%B8%B3%E0%B8%94%E0%B8%B1%E0%B8%9A%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%9C%E0%B8%AA%E0%B8%B2%E0%B8%99" title="タイ語: การเรียงลำดับแบบผสาน" lang="th" hreflang="th" data-title="การเรียงลำดับแบบผสาน" data-language-autonym="ไทย" data-language-local-name="タイ語" class="interlanguage-link-target">ไทย</a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Birle%C5%9Ftirmeli_s%C4%B1ralama" title="トルコ語: Birleştirmeli sıralama" lang="tr" hreflang="tr" data-title="Birleştirmeli sıralama" data-language-autonym="Türkçe" data-language-local-name="トルコ語" class="interlanguage-link-target">Türkçe</a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%B7%D0%BB%D0%B8%D1%82%D1%82%D1%8F%D0%BC" title="ウクライナ語: Сортування злиттям" lang="uk" hreflang="uk" data-title="Сортування злиттям" data-language-autonym="Українська" data-language-local-name="ウクライナ語" class="interlanguage-link-target">Українська</a></li><li class="interlanguage-link interwiki-uz mw-list-item"><a href="https://uz.wikipedia.org/wiki/Merge_Sort" title="ウズベク語: Merge Sort" lang="uz" hreflang="uz" data-title="Merge Sort" data-language-autonym="Oʻzbekcha / ўзбекча" data-language-local-name="ウズベク語" class="interlanguage-link-target">Oʻzbekcha / ўзбекча</a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/S%E1%BA%AFp_x%E1%BA%BFp_tr%E1%BB%99n" title="ベトナム語: Sắp xếp trộn" lang="vi" hreflang="vi" data-title="Sắp xếp trộn" data-language-autonym="Tiếng Việt" data-language-local-name="ベトナム語" class="interlanguage-link-target">Tiếng Việt</a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F" title="中国語: 归并排序" lang="zh" hreflang="zh" data-title="归并排序" data-language-autonym="中文" data-language-local-name="中国語" class="interlanguage-link-target">中文</a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F" title="広東語: 合併排序" lang="yue" hreflang="yue" data-title="合併排序" data-language-autonym="粵語" data-language-local-name="広東語" class="interlanguage-link-target">粵語</a></li> </ul> <div class="after-portlet after-portlet-lang"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q189057#sitelinks-wikipedia" title="言語間リンクを編集" class="wbc-editpage">リンクを編集</a></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="名前空間"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88" title="本文を閲覧 [c]" accesskey="c">ページ</a></li><li id="ca-talk" class="new vector-tab-noicon mw-list-item"><a href="/w/index.php?title=%E3%83%8E%E3%83%BC%E3%83%88:%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" rel="discussion" class="new" title="「本文ページについての議論」 (存在しないページ) [t]" accesskey="t">ノート</a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="別の言語に切り替える" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" >日本語 </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="表示"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88">閲覧</a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit" title="このページのソースコードを編集する [e]" accesskey="e">編集</a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=history" title="このページの過去の版 [h]" accesskey="h">履歴表示</a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="ページツール"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="ツール" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" >ツール </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">ツール</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">サイドバーに移動</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">非表示</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="その他の操作" > <div class="vector-menu-heading"> 操作 </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88">閲覧</a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit" title="このページのソースコードを編集する [e]" accesskey="e">編集</a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=history">履歴表示</a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> 全般 </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E3%83%AA%E3%83%B3%E3%82%AF%E5%85%83/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88" title="ここにリンクしている全ウィキページの一覧 [j]" accesskey="j">リンク元</a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E9%96%A2%E9%80%A3%E3%83%9A%E3%83%BC%E3%82%B8%E3%81%AE%E6%9B%B4%E6%96%B0%E7%8A%B6%E6%B3%81/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88" rel="nofollow" title="このページからリンクしているページの最近の更新 [k]" accesskey="k">関連ページの更新状況</a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%E3%81%AE%E3%82%A2%E3%83%83%E3%83%97%E3%83%AD%E3%83%BC%E3%83%89" title="ファイルをアップロードする [u]" accesskey="u">ファイルをアップロード</a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E7%89%B9%E5%88%A5%E3%83%9A%E3%83%BC%E3%82%B8%E4%B8%80%E8%A6%A7" title="特別ページの一覧 [q]" accesskey="q">特別ページ</a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&oldid=89273506" title="このページのこの版への固定リンク">この版への固定リンク</a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=info" title="このページについての詳細情報">ページ情報</a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%81%93%E3%81%AE%E3%83%9A%E3%83%BC%E3%82%B8%E3%82%92%E5%BC%95%E7%94%A8&page=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&id=89273506&wpFormIdentifier=titleform" title="このページの引用方法">このページを引用</a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:UrlShortener&url=https%3A%2F%2Fja.wikipedia.org%2Fwiki%2F%25E3%2583%259E%25E3%2583%25BC%25E3%2582%25B8%25E3%2582%25BD%25E3%2583%25BC%25E3%2583%2588">短縮URLを取得する</a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:QrCode&url=https%3A%2F%2Fja.wikipedia.org%2Fwiki%2F%25E3%2583%259E%25E3%2583%25BC%25E3%2582%25B8%25E3%2582%25BD%25E3%2583%25BC%25E3%2583%2588">QRコードをダウンロード</a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> 印刷/書き出し </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-create_a_book" class="mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%83%96%E3%83%83%E3%82%AF&bookcmd=book_creator&referer=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88">ブックの新規作成</a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:DownloadAsPdf&page=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=show-download-screen">PDF 形式でダウンロード</a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&printable=yes" title="このページの印刷用ページ [p]" accesskey="p">印刷用バージョン</a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> 他のプロジェクト </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Merge_sort" hreflang="en">コモンズ</a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q189057" title="関連付けられたデータリポジトリ項目へのリンク [g]" accesskey="g">ウィキデータ項目</a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="ページツール"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="表示"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">表示</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">サイドバーに移動</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">非表示</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">出典: フリー百科事典『ウィキペディア（Wikipedia）』</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="ja" dir="ltr"><table class="infobox" style="width:22em;"><caption itemprop="name" class="" style="">マージソート</caption><tbody><tr class="" style="" itemprop=""><td colspan="2" class="" style="text-align:center;" itemprop=""> <a href="/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Merge-sort-example-300px.gif" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif" decoding="async" width="300" height="180" class="mw-file-element" data-file-width="300" data-file-height="180" /></a><div style="">マージソートの例。まずリストを小さな単位に分け、二つのリストをそれぞれの要素の先頭を比較してマージする。最後までこの操作をくり返すと、リストはソートされている。</div></td></tr><tr class="" style="" itemprop=""><th scope="row" style="text-align:left; white-space:nowrap;">クラス</th><td class="" style="" itemprop=""> ソート</td></tr><tr class="" style="" itemprop=""><th scope="row" style="text-align:left; white-space:nowrap;">データ構造</th><td class="" style="" itemprop=""> 配列</td></tr><tr class="" style="" itemprop=""><th scope="row" style="text-align:left; white-space:nowrap;"><a href="https://en.wikipedia.org/wiki/Best,_worst_and_average_case" class="extiw" title="en:Best, worst and average case">最悪計算時間</a></th><td class="" style="" itemprop=""> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}"></td></tr><tr class="" style="" itemprop=""><th scope="row" style="text-align:left; white-space:nowrap;"><a href="https://en.wikipedia.org/wiki/Best,_worst_and_average_case" class="extiw" title="en:Best, worst and average case">最良計算時間</a></th><td class="" style="" itemprop=""> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}"> typical, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}"> natural variant</td></tr><tr class="" style="" itemprop=""><th scope="row" style="text-align:left; white-space:nowrap;"><a href="https://en.wikipedia.org/wiki/Best,_worst_and_average_case" class="extiw" title="en:Best, worst and average case">平均計算時間</a></th><td class="" style="" itemprop=""> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}"></td></tr><tr class="" style="" itemprop=""><th scope="row" style="text-align:left; white-space:nowrap;"><a href="https://en.wikipedia.org/wiki/Best,_worst_and_average_case" class="extiw" title="en:Best, worst and average case">最悪空間計算量</a></th><td class="" style="" itemprop=""> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}"> 外部記憶</td></tr></tbody></table> <figure class="mw-default-size mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Merge_sort_animation2.gif" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c5/Merge_sort_animation2.gif/220px-Merge_sort_animation2.gif" decoding="async" width="220" height="186" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/c/c5/Merge_sort_animation2.gif 1.5x" data-file-width="280" data-file-height="237" /></a><figcaption>マージソートの様子</figcaption></figure> マージソートは、<a href="/wiki/%E3%82%BD%E3%83%BC%E3%83%88" title="ソート">ソート</a>の<a href="/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0" title="アルゴリズム">アルゴリズム</a>で、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの<a href="/wiki/%E5%88%86%E5%89%B2%E7%B5%B1%E6%B2%BB%E6%B3%95" title="分割統治法">分割統治法</a>による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は<a href="/wiki/%E4%B8%A6%E5%88%97%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0" class="mw-redirect" title="並列コンピューティング">並列化</a>できる。 n個のデータを含む配列をソートする場合、最悪<a href="/wiki/%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96" title="計算複雑性理論">計算量</a><a href="/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7" title="ランダウの記号">O</a>(n log n)である。分割と統合の実装にもよるが、一般に<a href="/wiki/%E5%AE%89%E5%AE%9A%E3%82%BD%E3%83%BC%E3%83%88" title="安定ソート">安定なソート</a>を実装できる。<a href="/wiki/In-place%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0" title="In-placeアルゴリズム">インプレース</a>な（すなわち入力の記憶領域を出力にも使うので、追加の作業記憶領域を必要としない）バリエーションも提案されているが、一般には、O(n)の追加の作業記憶領域を必要とする<a href="#cite_note-algo-1">[1]</a>。 （ナイーブな）<a href="/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88" title="クイックソート">クイックソート</a>と比べると、最悪計算量は少ない<a href="#cite_note-algo-1">[1]</a>。<a href="/wiki/%E4%B9%B1%E6%95%B0" class="mw-redirect" title="乱数">ランダム</a>なデータでは通常、クイックソートのほうが速い。 1945年、<a href="/wiki/%E3%82%B8%E3%83%A7%E3%83%B3%E3%83%BB%E3%83%95%E3%82%A9%E3%83%B3%E3%83%BB%E3%83%8E%E3%82%A4%E3%83%9E%E3%83%B3" title="ジョン・フォン・ノイマン">フォン・ノイマン</a>によって考案された<a href="#cite_note-2">[2]</a>。 <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="アルゴリズム">アルゴリズム</h2>[<a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&section=1" title="節を編集: アルゴリズム">編集</a>]</div> 基本的な手順は以下の通りである。 <ol><li>データ列を分割する（通常、二等分する）</li> <li>分割された各データ列で、含まれるデータが1個ならそれを返し、2個以上ならステップ1から3を<a href="/wiki/%E5%86%8D%E5%B8%B0" title="再帰">再帰</a>的に適用してマージソートする</li> <li>二つのソートされたデータ列（1個であればそれ自身）を<a href="/wiki/%E3%83%9E%E3%83%BC%E3%82%B8" title="マージ">マージ</a>する</li></ol> ステップ1と2の途中（すなわち細分化するまでの部分）についてこのアルゴリズムの手順に含めず、あらかじめ局所的に整列されている多数の列が与えられるもの、とすることもある。後述する、テープをマージする手法の場合、最初のテープから主記憶を可能な限り全部使って整列できるだけ整列した部分列を、順次書き出したテープから始める。 ステップ3のマージでは、2本のデータ列の先頭同士を比べ小さい方をデータ列から取り出して出力し、残りのデータをもつ2本のデータ列に対して再帰的に同じ処理を、両方が空になるまで行う。ソートすべきデータ列が部分的に順次得られる場合、<a href="/wiki/%E3%82%AA%E3%83%B3%E3%83%A9%E3%82%A4%E3%83%B3%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0" title="オンラインアルゴリズム">オンラインアルゴリズム</a>として、部分データ列をソートして後でマージするという変形も可能である。 クイックソート等と同様、完全に細分化せずにスレッショルドとして適度に大きい個数を設定し、それ以下になった時点でなんらかの「ごく少数の対象専用の高速なコードによるソート」を併用するという高速化手法がある<a href="#cite_note-algo-1">[1]</a>。手順として書き出すと次のようになる。 <ol><li>データ列を分割する（通常、二等分する）</li> <li>分割された各データ列で、含まれるデータが設定個数以下ならそれを別の高速なアルゴリズムでソートして返し、設定個数超ならステップ1から3を<a href="/wiki/%E5%86%8D%E5%B8%B0" title="再帰">再帰</a>的に適用してマージソートする</li> <li>二つのソートされたデータ列を<a href="/wiki/%E3%83%9E%E3%83%BC%E3%82%B8" title="マージ">マージ</a>する</li></ol> 他に特殊な応用例として、外部ソートの1手法でテープ（のようなシーケンシャルアクセスメディア）に収められたデータをソートする、というものがある。最も単純な、4本のテープを2本ずつ使う「平衡2系列マージ」を例に説明する。まず元のデータから、利用可能な内部記憶をできるだけ使って、部分的に整列されている列をテープに書き出す。この時、2本のテープに交互に書き出すようにする。 次に、2本のテープのそれぞれの先頭部分にある、それぞれの部分列をマージしながら、別の2本のテープに交互に書き出す。この操作により、より長い整列した列が得られる。全てのマージが終わったら、コピー元とコピー先を入れ替え、同様に繰り返す。繰返し毎に各部分列の長さは約2倍に、列の個数は約半分になると期待できる。 最終的に、テープを切り替えることなく、1本のテープに全てのデータが出力されたら完了である。この技法はコンピュータがまだ高価で、テープが大容量外部記憶の主力だった時代にさかんに研究され、さまざまなバリエーションが編み出された。『<a href="/wiki/The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a>』の§5.4にそれらの詳細がある。 <div class="mw-heading mw-heading3"><h3 id="実装例">実装例</h3>[<a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&section=2" title="節を編集: 実装例">編集</a>]</div> <div class="mw-heading mw-heading4"><h4 id="C">C</h4>[<a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&section=3" title="節を編集: C">編集</a>]</div> <div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>#include <stdio.h> void merge(int A[], int B[], int left, int mid, int right) { int i = left; int j = mid; int k = 0; int l; while (i < mid && j < right) { if (A[i] <= A[j]) { B[k++] = A[i++]; } else { B[k++] = A[j++]; } } if (i == mid) { /* i側のAをBに移動し尽くしたので、j側も順番にBに入れていく */ while (j < right) { B[k++] = A[j++]; } } else { while (i < mid) { /* j側のAをBに移動し尽くしたので、i側も順番にBに入れていく */ B[k++] = A[i++]; } } for (l = 0; l < k; l++) { A[left + l] = B[l]; } } void merge_sort(int A[], int B[], int left, int right) { int mid; if (left == right || left == right - 1) { return; } mid = (left + right) / 2; merge_sort(A, B, left, mid); merge_sort(A, B, mid, right); merge(A, B, left, mid, right); } int main(void) { int a[10] = {8,4,7,2,1,3,5,6,9,10}; int b[10] = {0}; const int n = 10; int i; merge_sort(a, b, 0, n); for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } </pre></div> <div class="mw-heading mw-heading4"><h4 id="Ruby">Ruby</h4>[<a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&section=4" title="節を編集: Ruby">編集</a>]</div> <div class="mw-highlight mw-highlight-lang-ruby mw-content-ltr" dir="ltr"><pre>def mergesort lst return _mergesort_ lst.dup # 副作用で配列が壊れるので、複製を渡す end def _mergesort_ lst if (len = lst.size) <= 1 then return lst end # pop メソッドの返す値と副作用の両方を利用して、lst を二分する lst2 = lst.pop(len >> 1) return _merge_(_mergesort_(lst), _mergesort_(lst2)) end def _merge_ lst1, lst2 len1, len2 = lst1.size, lst2.size result = Array.new(len1 + len2) a, b = lst1[0], lst2[0] i, j, k = 0, 0, 0 loop { if a <= b then result[i] = a i += 1 ; j += 1 break unless j < len1 a = lst1[j] else result[i] = b i += 1 ; k += 1 break unless k < len2 b = lst2[k] end } while j < len1 do result[i] = lst1[j] i += 1 ; j += 1 end while k < len2 do result[i] = lst2[k] i += 1 ; k += 1 end return result end </pre></div> <div class="mw-heading mw-heading4"><h4 id="Haskell">Haskell</h4>[<a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&section=5" title="節を編集: Haskell">編集</a>]</div> （※ <a href="/wiki/Haskell" title="Haskell">Haskell</a>のリストは「長さを測って半分ずつに分ける」という操作には適さないため、要素を1個ずつ振り分ける関数を使っている。この実装では安定ではない） <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre>mergesort :: Ord t => [t] -> [t] mergesort lst = case lst of [] -> lst [_] -> lst _ -> merge (mergesort a) (mergesort b) where (a, b) = split lst merge [] [] = [] merge xxs [] = xxs merge [] yys = yys merge xxs@(x : xs) yys@(y : ys) | x < y = x : (merge xs yys) | otherwise = y : (merge xxs ys) split [] = ([], []) split ~(x : xs) = (x : zs, ys) where (ys, zs) = split xs </pre></div> <div class="mw-heading mw-heading4"><h4 id="Scheme">Scheme</h4>[<a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&section=6" title="節を編集: Scheme">編集</a>]</div> <div class="mw-highlight mw-highlight-lang-scheme mw-content-ltr" dir="ltr"><pre>;; use-modules は処理系 Guile 固有の機能である。 ;; SRFI 機能を使うための仕組み処理系に依る。 (use-modules (srfi srfi-1 )) ; split-at (use-modules (srfi srfi-11)) ; let-values (define (merge left-half right-half) (let loop ((ls left-half) (rs right-half) (result (list))) (cond ((null? rs) (append (reverse result) ls)) ((null? ls) (append (reverse result) rs)) (else (let ((l (car ls)) (r (car rs))) (if (<= l r) (loop (cdr ls) rs (cons l result)) (loop ls (cdr rs) (cons r result)))))))) (define (merge-sort xs) (cond ((null? xs ) xs) ((null? (cdr xs)) xs) (else (let-values (((left-half right-half) (split-at xs (quotient (length xs) 2)))) (merge (merge-sort left-half) (merge-sort right-half)))))) </pre></div> <div class="mw-heading mw-heading2"><h2 id="アルゴリズムの動作例">アルゴリズムの動作例</h2>[<a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&section=7" title="節を編集: アルゴリズムの動作例">編集</a>]</div> 初期データ: 8 4 3 7 6 5 2 1 <ol><li>データ列を二分割する。 <dl><dd>8 4 3 7 | 6 5 2 1</dd></dl></li> <li>もう一度、二分割する。 <dl><dd>8 4 | 3 7 | 6 5 | 2 1</dd></dl></li> <li>各データ列にデータ数が2以下になったところで、各データ列内のデータをソートする。 <dl><dd>4 8 | 3 7 | 5 6 | 1 2</dd></dl></li> <li>この例の場合は、右2つのデータ列、左2つのデータ列をそれぞれマージとソートし、2つのデータ列にする。 <dl><dd>3 4 7 8 | 1 2 5 6</dd></dl></li> <li>2つのデータ列をマージとソートする。 <dl><dd>1 2 3 4 5 6 7 8</dd></dl></li></ol> <div class="mw-heading mw-heading2"><h2 id="脚注">脚注</h2>[<a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&section=8" title="節を編集: 脚注">編集</a>]</div> <ol class="references"> <li id="cite_note-algo-1">^ <a href="#cite_ref-algo_1-0">a</a> <a href="#cite_ref-algo_1-1">b</a> <a href="#cite_ref-algo_1-2">c</a> <cite style="font-style:normal" class="citation book"><a href="/wiki/%E5%A5%A5%E6%9D%91%E6%99%B4%E5%BD%A6" title="奥村晴彦">奥村晴彦</a>『C言語による最新アルゴリズム事典』<a href="/wiki/%E6%8A%80%E8%A1%93%E8%A9%95%E8%AB%96%E7%A4%BE" title="技術評論社">技術評論社</a>、1991年、267頁。<style data-mw-deduplicate="TemplateStyles:r101121245">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:var(--color-success,#3a3);margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}</style><a href="/wiki/ISBN" title="ISBN">ISBN</a> <a href="/wiki/%E7%89%B9%E5%88%A5:%E6%96%87%E7%8C%AE%E8%B3%87%E6%96%99/4-87408-414-1" title="特別:文献資料/4-87408-414-1">4-87408-414-1</a>。</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=C%E8%A8%80%E8%AA%9E%E3%81%AB%E3%82%88%E3%82%8B%E6%9C%80%E6%96%B0%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E4%BA%8B%E5%85%B8&rft.aulast=%E5%A5%A5%E6%9D%91%E6%99%B4%E5%BD%A6&rft.au=%E5%A5%A5%E6%9D%91%E6%99%B4%E5%BD%A6&rft.date=1991&rft.pages=267%E9%A0%81&rft.pub=%5B%5B%E6%8A%80%E8%A1%93%E8%A9%95%E8%AB%96%E7%A4%BE%5D%5D&rft.isbn=4-87408-414-1&rfr_id=info:sid/ja.wikipedia.org:%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88">  </li> <li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite style="font-style:normal" class="citation book" id="CITEREFKnuth1998"><a href="/wiki/Donald_Knuth" class="mw-redirect" title="Donald Knuth">Knuth, Donald</a> (1998). “Section 5.2.4: Sorting by Merging”. Sorting and Searching. <a href="/wiki/The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a>. 3 (2nd ed.). Addison-Wesley. pp. 158. <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r101121245"><a href="/wiki/ISBN" title="ISBN">ISBN</a> <a href="/wiki/%E7%89%B9%E5%88%A5:%E6%96%87%E7%8C%AE%E8%B3%87%E6%96%99/0-201-89685-0" title="特別:文献資料/0-201-89685-0">0-201-89685-0</a></cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.btitle=Section+5.2.4%3A+Sorting+by+Merging&rft.atitle=Sorting+and+Searching&rft.aulast=Knuth&rft.aufirst=Donald&rft.au=Knuth%2C%26%2332%3BDonald&rft.date=1998&rft.series=%5B%5BThe+Art+of+Computer+Programming%5D%5D&rft.volume=3&rft.pages=pp.%26nbsp%3B158&rft.edition=2nd&rft.pub=Addison-Wesley&rft.isbn=0-201-89685-0&rfr_id=info:sid/ja.wikipedia.org:%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88">  </li> </ol> <div class="mw-heading mw-heading2"><h2 id="関連項目">関連項目</h2>[<a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&section=9" title="節を編集: 関連項目">編集</a>]</div> <ul><li><a href="/wiki/%E3%83%9E%E3%83%BC%E3%82%B8" title="マージ">マージ</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="外部リンク">外部リンク</h2>[<a href="/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&section=10" title="節を編集: 外部リンク">編集</a>]</div> <ul><li><a rel="nofollow" class="external text" href="http://www.codecodex.com/wiki/Merge_sort">マージソートコード(英語)</a></li></ul> <div class="navbox" aria-labelledby="ソート" style="border-collapse:collapse;padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="background:transparent;color:inherit;min-width:100%;border-spacing:0px;border-collapse:separate"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div style="float:left;width:6em;text-align:left"><div class="noprint plainlinks navbar hlist" style="white-space:nowrap;font-size:60%;font-weight:normal;background-color:transparent;padding:0;color:#000;;border:none;"><ul style="display:inline"><li><a href="/wiki/Template:%E3%82%BD%E3%83%BC%E3%83%88" title="Template:ソート">表</a></li><li><a href="/w/index.php?title=Template%E2%80%90%E3%83%8E%E3%83%BC%E3%83%88:%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「Template‐ノート:ソート」 (存在しないページ)">話</a></li><li><a class="external text" href="https://ja.wikipedia.org/w/index.php?title=Template%3A%E3%82%BD%E3%83%BC%E3%83%88&action=edit">編</a></li><li><a class="external text" href="https://ja.wikipedia.org/w/index.php?title=Template%3A%E3%82%BD%E3%83%BC%E3%83%88&action=history">歴</a></li></ul></div></div><div id="ソート" style="font-size:110%;margin:0 6em"><a href="/wiki/%E3%82%BD%E3%83%BC%E3%83%88" title="ソート">ソート</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">理論</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96" title="計算複雑性理論">計算複雑性理論</a></li> <li><a href="/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7" title="ランダウの記号">ランダウの記号</a></li> <li><a href="/wiki/%E5%85%A8%E9%A0%86%E5%BA%8F" title="全順序">全順序</a></li> <li><a href="/wiki/%E3%83%AA%E3%82%B9%E3%83%88_(%E6%8A%BD%E8%B1%A1%E3%83%87%E3%83%BC%E3%82%BF%E5%9E%8B)" title="リスト (抽象データ型)">リスト</a></li> <li><a href="/wiki/%E3%82%BD%E3%83%BC%E3%83%88#安定ソート" title="ソート">安定性</a></li> <li><a href="/wiki/%E3%82%BD%E3%83%BC%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF" title="ソーティングネットワーク">ソーティングネットワーク</a></li> <li><a href="/w/index.php?title=%E6%AF%94%E8%BC%83%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「比較ソート」 (存在しないページ)">比較ソート</a>（<a href="https://en.wikipedia.org/wiki/Comparison_sort" class="extiw" title="en:Comparison sort">英語版</a>）</li> <li><a href="/w/index.php?title=%E6%95%B4%E6%95%B0%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「整数ソート」 (存在しないページ)">整数ソート</a>（<a href="https://en.wikipedia.org/wiki/Integer_sorting" class="extiw" title="en:Integer sorting">英語版</a>）</li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">交換ソート</th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88" title="バブルソート">バブルソート</a></li> <li><a href="/wiki/%E3%82%B7%E3%82%A7%E3%83%BC%E3%82%AB%E3%83%BC%E3%82%BD%E3%83%BC%E3%83%88" title="シェーカーソート">シェーカーソート</a></li> <li><a href="/wiki/%E5%A5%87%E5%81%B6%E8%BB%A2%E7%BD%AE%E3%82%BD%E3%83%BC%E3%83%88" title="奇偶転置ソート">奇偶転置ソート</a></li> <li><a href="/wiki/%E3%82%B3%E3%83%A0%E3%82%BD%E3%83%BC%E3%83%88" title="コムソート">コムソート</a></li> <li><a href="/wiki/%E3%83%8E%E3%83%BC%E3%83%A0%E3%82%BD%E3%83%BC%E3%83%88" title="ノームソート">ノームソート</a></li> <li><a href="/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88" title="クイックソート">クイックソート</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">選択ソート</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88" title="選択ソート">選択ソート</a></li> <li><a href="/wiki/%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88" title="ヒープソート">ヒープソート</a></li> <li><a href="/w/index.php?title=%E3%82%B9%E3%83%A0%E3%83%BC%E3%82%B9%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「スムースソート」 (存在しないページ)">スムースソート</a></li> <li><a href="/w/index.php?title=%E3%83%87%E3%82%AB%E3%83%AB%E3%83%88%E6%9C%A8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「デカルト木ソート」 (存在しないページ)">デカルト木ソート</a></li> <li><a href="/w/index.php?title=%E3%83%88%E3%83%BC%E3%83%8A%E3%83%A1%E3%83%B3%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「トーナメントソート」 (存在しないページ)">トーナメントソート</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">挿入ソート</th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88" title="挿入ソート">挿入ソート</a></li> <li><a href="/wiki/%E3%82%B7%E3%82%A7%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88" title="シェルソート">シェルソート</a></li> <li><a href="/w/index.php?title=%E3%83%84%E3%83%AA%E3%83%BC%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「ツリーソート」 (存在しないページ)">ツリーソート</a></li> <li><a href="/wiki/%E5%9B%B3%E6%9B%B8%E9%A4%A8%E3%82%BD%E3%83%BC%E3%83%88" title="図書館ソート">図書館ソート</a></li> <li><a href="/w/index.php?title=%E3%83%9A%E3%82%A4%E3%82%B7%E3%82%A7%E3%83%B3%E3%82%B9%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「ペイシェンスソート」 (存在しないページ)">ペイシェンスソート</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">マージソート</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a class="mw-selflink selflink">マージソート</a></li> <li><a href="/w/index.php?title=%E5%A4%9A%E5%B1%A4%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「多層マージソート」 (存在しないページ)">多層マージソート</a></li> <li><a href="/w/index.php?title=%E3%82%B9%E3%83%88%E3%83%A9%E3%83%B3%E3%83%89%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「ストランドソート」 (存在しないページ)">ストランドソート</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">非比較ソート</th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%E5%9F%BA%E6%95%B0%E3%82%BD%E3%83%BC%E3%83%88" title="基数ソート">基数ソート</a></li> <li><a href="/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88" title="バケットソート">バケットソート</a></li> <li><a href="/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88" title="バケットソート">計数ソート</a></li> <li><a href="/w/index.php?title=%E3%83%97%E3%83%AD%E3%82%AD%E3%82%B7%E3%83%9E%E3%83%83%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「プロキシマップソート」 (存在しないページ)">プロキシマップソート</a></li> <li><a href="/wiki/%E9%B3%A9%E3%81%AE%E5%B7%A3%E3%82%BD%E3%83%BC%E3%83%88" title="鳩の巣ソート">鳩の巣ソート</a></li> <li><a href="/w/index.php?title=%E3%83%90%E3%83%BC%E3%82%B9%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「バーストソート」 (存在しないページ)">バーストソート</a></li> <li><a href="/wiki/%E3%83%93%E3%83%BC%E3%82%BA%E3%82%BD%E3%83%BC%E3%83%88" title="ビーズソート">ビーズソート</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">並行ソート</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%E3%83%90%E3%82%A4%E3%83%88%E3%83%8B%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88" title="バイトニックソート">バイトニックソート</a></li> <li><a href="/wiki/%E3%83%90%E3%83%83%E3%83%81%E3%83%A3%E3%83%BC%E5%A5%87%E5%81%B6%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88" title="バッチャー奇偶マージソート">バッチャー奇偶マージソート</a></li> <li><a href="/wiki/%E3%82%B7%E3%82%A7%E3%82%A2%E3%82%BD%E3%83%BC%E3%83%88" title="シェアソート">シェアソート</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">混成ソート</th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%E3%83%86%E3%82%A3%E3%83%A0%E3%82%BD%E3%83%BC%E3%83%88" title="ティムソート">ティムソート</a></li> <li><a href="/wiki/%E3%82%A4%E3%83%B3%E3%83%88%E3%83%AD%E3%82%BD%E3%83%BC%E3%83%88" title="イントロソート">イントロソート</a></li> <li><a href="/w/index.php?title=J%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「Jソート」 (存在しないページ)">Jソート</a></li> <li><a href="/w/index.php?title=%E3%82%A2%E3%83%B3%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「アンシャッフルソート」 (存在しないページ)">アンシャッフルソート</a>（<a href="https://en.wikipedia.org/wiki/UnShuffle_sort" class="extiw" title="en:UnShuffle sort">英語版</a>）</li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">その他</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%E3%83%88%E3%83%9D%E3%83%AD%E3%82%B8%E3%82%AB%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88" title="トポロジカルソート">トポロジカルソート</a></li> <li><a href="/w/index.php?title=%E3%83%91%E3%83%B3%E3%82%B1%E3%83%BC%E3%82%AD%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「パンケーキソート」 (存在しないページ)">パンケーキソート</a></li> <li><a href="/wiki/%E3%82%B9%E3%83%91%E3%82%B2%E3%83%86%E3%82%A3%E3%82%BD%E3%83%BC%E3%83%88" title="スパゲティソート">スパゲティソート</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">非効率的/ ユーモラスソート</th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%E3%83%9C%E3%82%B4%E3%82%BD%E3%83%BC%E3%83%88" title="ボゴソート">ボゴソート</a></li> <li><a href="/wiki/%E3%82%B9%E3%83%88%E3%82%A5%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88" title="ストゥージソート">ストゥージソート</a></li> <li><a href="/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88#スリープソート" title="バケットソート">スリープソート</a></li> <li><a href="/w/index.php?title=%E3%82%A8%E3%83%A9%E3%83%BC%E3%82%BD%E3%83%BC%E3%83%88&action=edit&redlink=1" class="new" title="「エラーソート」 (存在しないページ)">エラーソート</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"> <a href="/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Folder_Hexagonal_Icon.svg" class="mw-file-description" title="カテゴリ"><img alt="カテゴリ" src="//upload.wikimedia.org/wikipedia/commons/thumb/4/48/Folder_Hexagonal_Icon.svg/16px-Folder_Hexagonal_Icon.svg.png" decoding="async" width="16" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/48/Folder_Hexagonal_Icon.svg/24px-Folder_Hexagonal_Icon.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/48/Folder_Hexagonal_Icon.svg/32px-Folder_Hexagonal_Icon.svg.png 2x" data-file-width="36" data-file-height="31" /></a> <a href="/wiki/Category:%E3%82%BD%E3%83%BC%E3%83%88" title="Category:ソート">カテゴリ</a></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">「<a dir="ltr" href="https://ja.wikipedia.org/w/index.php?title=マージソート&oldid=89273506">https://ja.wikipedia.org/w/index.php?title=マージソート&oldid=89273506</a>」から取得</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/%E7%89%B9%E5%88%A5:%E3%82%AB%E3%83%86%E3%82%B4%E3%83%AA" title="特別:カテゴリ">カテゴリ</a>: <ul><li><a href="/wiki/Category:%E3%82%BD%E3%83%BC%E3%83%88" title="Category:ソート">ソート</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> 最終更新 2022年4月29日 (金) 20:16 （日時は<a href="/wiki/%E7%89%B9%E5%88%A5:%E5%80%8B%E4%BA%BA%E8%A8%AD%E5%AE%9A#mw-prefsection-rendering" title="特別:個人設定">個人設定</a>で未設定ならば<a href="/wiki/%E5%8D%94%E5%AE%9A%E4%B8%96%E7%95%8C%E6%99%82" title="協定世界時">UTC</a>）。</li> <li id="footer-info-copyright">テキストは<a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.ja">クリエイティブ・コモンズ表示-継承ライセンス</a>のもとで利用できます。追加の条件が適用される場合があります。詳細については<a class="external text" href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use">利用規約</a>を参照してください。</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/ja">プライバシー・ポリシー</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:%E3%82%A6%E3%82%A3%E3%82%AD%E3%83%9A%E3%83%87%E3%82%A3%E3%82%A2%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6">ウィキペディアについて</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:%E5%85%8D%E8%B2%AC%E4%BA%8B%E9%A0%85">免責事項</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">行動規範</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">開発者</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/ja.wikipedia.org">統計</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookieに関する声明</a></li> <li id="footer-places-mobileview"><a href="//ja.m.wikipedia.org/w/index.php?title=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">モバイルビュー</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-6fgbm","wgBackendResponseTime":190,"wgPageParseReport":{"limitreport":{"cputime":"0.224","walltime":"0.968","ppvisitednodes":{"value":2516,"limit":1000000},"postexpandincludesize":{"value":40343,"limit":2097152},"templateargumentsize":{"value":3234,"limit":2097152},"expansiondepth":{"value":21,"limit":100},"expensivefunctioncount":{"value":7,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":41839,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 599.929 1 -total"," 18.84% 113.053 2 Template:Cite_book"," 14.64% 87.846 1 Template:Citation/core-ja-jp"," 10.98% 65.867 2 Template:Citation/identifier"," 10.55% 63.292 2 Template:ISBN2"," 8.22% 49.339 1 Template:ソート"," 6.52% 39.135 2 Template:Catalog_lookup_link"," 5.72% 34.303 1 Template:Navbox"," 3.54% 21.234 1 Template:Infobox_algorithm"," 3.06% 18.370 1 Template:Citation/core"]},"scribunto":{"limitreport-timeusage":{"value":"0.024","limit":"10.000"},"limitreport-memusage":{"value":1350066,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-5ff89fd665-xjd9p","timestamp":"20241024102851","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"\u30de\u30fc\u30b8\u30bd\u30fc\u30c8","url":"https:\/\/ja.wikipedia.org\/wiki\/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88","sameAs":"http:\/\/www.wikidata.org\/entity\/Q189057","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q189057","author":{"@type":"Organization","name":"\u30a6\u30a3\u30ad\u30e1\u30c7\u30a3\u30a2\u30d7\u30ed\u30b8\u30a7\u30af\u30c8\u3078\u306e\u8ca2\u732e\u8005"},"publisher":{"@type":"Organization","name":"\u30a6\u30a3\u30ad\u30e1\u30c7\u30a3\u30a2\u8ca1\u56e3","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-08-09T06:14:22Z","dateModified":"2022-04-29T20:16:53Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/c\/cc\/Merge-sort-example-300px.gif","headline":"\u30bd\u30fc\u30c8\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u3072\u3068\u3064"}</script> </body> </html>