I was asked to write a simple merge-sort implementation as the initial warm-up part of an interview. (Meaning knowing how to implement merge-sort is a must-have requirement rather than an optional knowledge).

So what’s the algorithm for Merge Sort? We need to divide and conquer! Split up the list into a number of sublists, apply mergesort to each of them (recursively) and merge them.

## Merge Sort Algorithm

1. Divide the unsorted list into 2 sublists.
2. Sort them (using recursion of merge sort).
3. Merge the two sorted list in a merge step to produce 1 sorted list.

Since writing a merge-sort implementation is not too hard and not complicated our assumptions stage should not take more than 30 seconds. We should just state our knowledge about merge-sort:

• Worst case Time Complexity: O(nlog(n))
• Auxiliary Space Complexity: O(n)

For an even deeper display of knowledge you could try to compare it to one of the other most popular sorting algorithms like quicksort. (For a quick rundown you can check Quick-sort implementation in Java) This should probably be enough and we can just get down to the coding part. Our language of choice will be Java.

## Merge-sort Implementation

I am honestly not a fan of interviews which ask you to blurt “well-known” algorithms, but oh well, now if you now get asked a basic sorting question at the beginning of your interview you will probably be able to analyze it and put out a quick solution.
Hope you guys enjoyed it… and I’ll see you guys next time ;D

The following two tabs change content below.

#### Ajk

If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media ðŸ™‚