روش تقسیم و حل، تقسیم مسأله به زیرمسألههای کوچکتر و یکسان با مسألهی اولیه است که با ادغام جواب این زیرمسألهها بتوان مسألهی اصلی را سادهتر حل کرد. با این کار زمان حل مسأله کاهش مییابد.
الگوریتمهای مرتبسازی سریع، مرتبسازی ادغامی و جستجوی دودویی از الگوریتمهای معروف تقسیم و حل هستند.
تعریف مسأله: آرایه داده شده را به صورت صعودی یا نزولی مرتب کنید.
مرتبسازی سریع: در این الگوریتم یک عنصر به عنوان محور انتخاب میشود و بر اساس آن آرایه را به دو قسمت عناصر کوچکتر و بزرگتر تقسیم میکنیم. هر کدام از این قسمتها به صورت بازگشتی مرتب میشوند. اگر عنصر میانه به عنوان محور انتخاب شود، زمان الگوریتم $O(n\log n)$ خواهد شد.
مرتبسازی ادغامی: در ابتدای کار آرایه را به طور دلخواه به دو قسمت مساوی تقسیم میکنیم و هر قسمت را مرتب میکنیم. سپس بزرگترین عنصر هر قسمت را در آرایهی جواب کپی میکنیم و این کار را ادامه میدهیم تا عناصر هر دو آرایه تمام شوند. این کار به صورت بازگشتی آرایه را مرتب میکند و زمان آن $O(n\log n)$ است.
تحلیل: بهترین زمان الگوریتمهای مرتبسازی مقایسهای $O(n\log n)$ است.
پیادهسازی:
پیادهسازی الگوریتم مرتب سازی در زبان $C$، به صورت آماده در کتابخانه استاندارد $algorithm.h$ با نام $sort(begin,end)$ وجود دارد که $begin$ شروع و $end$ پایان آرایه را نشان میدهد. برای استفاده از این تابع برای مرتبسازی دلخواه خودتان، میتوانید تابع مقایسه دو عنصر را بنویسید و به عنوان ورودی به آن بدهید. مثالی از پیادهسازی این الگوریتم برای نوع دادهای $vector$ که یک آرایه پویا است در [[http://www.cplusplus.com/reference/algorithm/sort/ C در کتابخانه استاندارد algorithm.h
پیاده سازی شده است و با نام lower_bound(begin,end, key)
وجود دارد که در آن begin
شروع آرایه، end
پایان آرایه و key
کلید آرایه است. اشکال پیشرفتهتری از این تابع هم پیادهسازی شدهاند (قسمت جستجوی دودویی را ببینید).
این الگوریتم در زبان Java در Collections.binarySearch
تعریف شده است.
جستجوی دودویی روی بازه مقادیر:
جستجوی دودویی را میتوان برای به دست آوردن جواب یک مسأله که بازه مقادیر مجاز جواب آن را میدانیم (مثلاً بازهی اعداد صحیح ۱ تا ۱۰۰) به کار برد، به شرطی که هر بار بتوانیم نیمی از بازهی مقادیر را حذف کنیم. این اتفاق زمانی میافتد که مقادیر ورودی بر حسب مقادیر خروجی یکنوا باشند.
فرض کنید میخواهیم یک ماتریس $A_{m\times m}$ را به توان $n$ برسانیم. برای این کار از رابطهی بازگشتی زیر میتوانیم کمک بگیریم:
\[
A^n = \left\{
\begin{array}{l l}
\left( A ^{\lfloor n/2\rfloor} \right)^2\quad &\text{if n mod 2 = 0}
\left( A ^{\lfloor n/2\rfloor} \right)^2\times A \quad &\text{if n mod 2 = 1}
\end{array}\right.
\]
رابطهی بازگشتی قبل را میتوان با نگه داشتن جواب هر مرحله در زمان $O(m^2\log n)$ به دست آورد. از این روش برای به توان رساندن اعداد در زمان $O(\log n)$ هم میتوان استفاده کرد (اگر نخواهیم از تابع $pow$ استفاده کنیم. همچنین راه حل سریعتر برای ضریب ماتریسها هم وجود دارد.
الگوریتمهای مرتبسازی برای حالتهای خاص وجود دارند که در زمان خطی نسبت به تعداد عناصر کار میکنند. مرتبسازی مبنا و مرتبسازی سطلی از مثالهای معروف این مرتبسازیها هستند.