# Divide and conquer algorithms

A hacker on a roll may be able to produce–in a period of a few months–something that a small development group (say, 7-8 people) would have a hard time getting together over a year. IBM used to report that certain programmers might be as much as 100 times as productive as other workers, or more. Peter Seebach

## Merge sort

Language Java | Level Intermediate | Category Algorithms | August 3, 2015 10:31 pm

### Algorithm Problem Description

Merge sort is a divide and conquers and comparison-based sorting algorithm. It divide the array into subarray and conquer recursively sorting two subarrays. It combines the results into a final array.

#### Dive

Divide the problem into small subproblems.

#### Conquer

Solve the subproblem using recursive function.

#### Combine

Combine the sub solution into solution.

Merge sort can be implemented Top-down and Bottom-up. Top down merge sort split the list into sub list and sort the sub list. Finally, it merges sorted sublist into a single sorted list. Bottom up merge sort treats array of sub list and iteratively merges sub-lists back and forth between two buffers.

Merge sort uses for linked list sorting, external sorting on the tab. It is stable sort compare then other sorting algorithm.

Write a program to take the un-sorted array and sort the array using Merge sort.

### Output

```

Unsorted array before sorting: [12, 11, 13, 5, 6, 7]
Sorted array After Merge sort sorting: [5, 6, 7, 11, 12, 13]

```