Press "Enter" to skip to content

Mergesort implementation

Ajk 0

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.
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 🙂