Divide and conquer is an algorithm for solving a problem by the following steps

• Divide recursively the problem into non-overlapping subproblems until these become simple enough to be solved directly
• Conquer the subproblems by solving them recursively. If they are small enough, solve them as base cases
• Combine the solution to the subproblems into the solution for the original problem

Let's see a specific example

### Merge Sort

Merge sort is an efficient sorting algorithm using the Divide and conquer algorithm

• It divides the unsorted list into N sublists until each containing one element
• Sort/Conquer the sublists by solving them as base cases, a list of one element is considered sorted
• Repeatedly merge/combine sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list

### Implementation example

``````
``````
Share to social

#### Giau Ngo

Giau Ngo is a software engineer, creator of HelloKoding. He loves coding, blogging, and traveling. You can find him on Twitter, GitHub and LinkedIn
{"ft_lang_label":"__label__en","ft_lang_prob":0.92194444,"math_prob":0.7058343,"size":876,"snap":"2020-45-2020-50","text_gpt3_token_len":177,"char_repetition_ratio":0.13073395,"word_repetition_ratio":0.0,"special_character_ratio":0.17694063,"punctuation_ratio":0.027972028,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9806499,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-10-19T22:13:20Z\",\"WARC-Record-ID\":\"<urn:uuid:bed2bf0a-a2fa-4b81-afa9-47e590427154>\",\"Content-Length\":\"49278\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a85475d6-b8dc-49b6-97cc-b3bb30aaede7>\",\"WARC-Concurrent-To\":\"<urn:uuid:b3c0be12-036a-4bd5-ba2e-b37f795424e3>\",\"WARC-IP-Address\":\"76.76.21.21\",\"WARC-Target-URI\":\"https://hellokoding.com/divide-and-conquer/\",\"WARC-Payload-Digest\":\"sha1:WWYY7PWT7OFQ6JQN4PN5OTPIL5FWH7M2\",\"WARC-Block-Digest\":\"sha1:3MITIPJHXKOIX2F5ACDL3C6FQIDBRUBG\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-45/CC-MAIN-2020-45_segments_1603107866404.1_warc_CC-MAIN-20201019203523-20201019233523-00030.warc.gz\"}"}