# Merge Sort in Java

## Merge Sort in Java Programming Language

Merge Sort is a Divide & Conquer principle based algorithm, like  its cousin Quick  Sort. The main idea of merge sort is to divide large data-sets into smaller sets of data, and then solve them. Merge Sort is a recursive algorithm, it divides the given array into smaller half’s and then calls itself repeatedly to solve them.

 Time Complexity Θ(n Log n) Best Case Ω(n Log n) Worst Case O(n Log n) Space Complexity O(n)

## Steps for Merge Sort in Java

#### Divide

• The original array is divided into sub-arrays.
• The sub-arrays are further divided into further sub-arrays until they contain a single element using recursion.

#### Conquering/ Merging

• Then the sub-lists are combined together in the desired (sorted) order.
• The time complexity of the merge sort is O(n log n) for best/ worst / average cases.

## Program for Merge Sort in Java

We will look at two different variations –

• Method 1: Works with two sub-arrays
• Method 2: Works with one sub-array

The space complexity is the same i.e. O(n) in both cases as even though there are two subarrays in method 1 they in total have n array items and method 2 also with one single array also has n array items.

## Merge Sort Analysis

• Merge sort is quick algorithm and does sorting in only O(n log n) time
• However, it comes with a cost, which is extra space complexity which is too high in comparison to others which is o(n)
• While, one good thing is there that for all cases, the time complexity remains the same i.e. average, best, worst

## Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.