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
- Divide the unsorted list into 2 sublists.
- Sort them (using recursion of merge sort).
- 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
/* * @Author: Ajk Palikuqi * * @Question: How To Implement MergeSort in Java */ package iqLib.sortLib; public class MergeSort { private int[] numbers; private int[] tempMergeArray; private int length; public static void main(String[] args) { int[] numbers = {2, 5, 7, 2, 1, 77, 4, 55, 333, 2, 31, 51}; MergeSort ms = new MergeSort(); ms.mergeSort(numbers); for (int i = 0; i < numbers.length; ++i) { System.out.println(numbers[i]); } } public void mergeSort(int[] numbers) { this.numbers = numbers; length = numbers.length; tempMergeArray = new int[length]; mergeSortHelper(0, length - 1); } public void mergeSortHelper(int start, int end) { if (start < end) { int mid = (start + end) / 2; mergeSortHelper(start, mid); mergeSortHelper(mid + 1, end); merge(start, mid, end); } } public void merge(int start, int mid, int end) { System.arraycopy(numbers, start, tempMergeArray, start, end-start+1); for (int i = start; i <= end; ++i) { tempMergeArray[i] = numbers[i]; } int i = start; int j = mid + 1; int k = start; while (i <= mid && j <= end) { if (tempMergeArray[i] <= tempMergeArray[j]) { numbers[k] = tempMergeArray[i]; ++i; } else { numbers[k] = tempMergeArray[j]; ++j; } ++k; } while (i <= mid) { numbers[k] = tempMergeArray[i]; ++i; ++k; } } } |
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
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017