Divide-and-conquer algorithm: Difference between revisions

Revision as of 21:32, 18 June 2019

Revision as of 08:14, 23 June 2019

Line 9:

== Divide and conquer ==

[[File:Merge sort algorithm diagram.svg|thumb|Divide-and-conquer approach to sort the list (38, 27, 43, 3, 9, 82, 10) in increasing order. ''Upper half:'' splitting into sublists; ''mid:'' a one-element list is trivially sorted; ''lower half:'' composing sorted sublists.]]

The divide-and-conquer paradigm is often used to find thean optimal solution of a problem. Its basic idea is to decompose a given problem into two or more similar, but simpler, subproblems, to solve them in turn, and to compose their solutions to solve the given problem. Problems of sufficient simplicity are solved directly.

For example, to sort a given list of ''n'' natural numbers, split it into two lists of about ''n''/2 numbers each, sort each of them in turn, and interleave both results appropriately to obtain the sorted version of the given list (see the picture). This approach is known as the [[merge sort]] algorithm.