The two sorting algorithms we've seen so far, selection sort and insertion sort, have worst-case running times of Θ(n2) \Theta(n^2) . When the size of the input array is large, these algorithms can take a long time to run. In this tutorial and the next one, we'll see two other sorting algorithms, merge sort and quicksort, whose running times are better. In particular, merge sort runs in Θ(nlgn) \Theta(n \lg n) time in all cases, and quicksort runs in Θ(nlgn) \Theta(n \lg n) time in the best case and on average, though its worst-case running time is Θ(n2) \Theta(n^2) . Here's a table of these four sorting algorithms and their running times:
অ্যালগোরিদমসবচেয়ে খারাপ ক্ষেত্রে এর রান করার সময়কালসবচেয়ে ভালো ক্ষেত্রে রান করার সময়গড়-ক্ষেত্রে এর রান করার সময়
সিলেকশন সর্টΘ(n2) \Theta(n^2) Θ(n2) \Theta(n^2) Θ(n2) \Theta(n^2)
ইনসারশন সর্টΘ(n2) \Theta(n^2) Θ(n2) \Theta(n^2)
মার্জ সর্টΘ(nlgn) \Theta(n \lg n) Θ(nlgn) \Theta(n \lg n) Θ(nlgn) \Theta(n \lg n)
কুইকসর্টΘ(n2) \Theta(n^2) Θ(nlgn) \Theta(n \lg n) Θ(nlgn) \Theta(n \lg n)

ডিভাইড-এন্ড-কনকার

Both merge sort and quicksort employ a common algorithmic paradigm based on recursion. This paradigm, divide-and-conquer, breaks a problem into subproblems that are similar to the original problem, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem. Because divide-and-conquer solves subproblems recursively, each subproblem must be smaller than the original problem, and there must be a base case for subproblems. You should think of a divide-and-conquer algorithm as having three parts:
  1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
  2. Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
  3. Combine the solutions to the subproblems into the solution for the original problem.
You can easily remember the steps of a divide-and-conquer algorithm as divide, conquer, combine. Here's how to view one step, assuming that each divide step creates two subproblems (though some divide-and-conquer algorithms create more than two):
আমরা যদি আরও দুইটি পুনরাবৃত্তির ধাপে এটা বিস্তৃত করি, তাহলে এটা দেখতে এমন হবে:
Because divide-and-conquer creates at least two subproblems, a divide-and-conquer algorithm makes multiple recursive calls.

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দ্বারা লাইসেন্সকৃত।