# Merge Sort: Divide and Conquer Approach

Merge sort is classic example of divide and conquer algorithm approach.

Divide and Conquer Algorithm Design approach: The idea is simple, as the term suggest, we try to divide the original problem into multiple smaller problems. These small problems are solved and the solutions then are merged into one final solution.

The concept is used in merge sorting. Input to any sorting algorithm is a random list (array). For sake of this example let’s take a random array of numbers as input.

Divide Phase: Divide the main array into smaller arrays upto a level that it can sorted easily.

Conquer: Merge these entire sorted arrays into the final solution array.

Example – Lets say we have an array

Original: 99, 23, 45, 12, 67, 28, 09, 98, 44, 84

Divide Phase

Arr1: 99, 23, 45, 12, 67                | Arr2:   28, 09, 98, 44, 84

99, 23, 45                    | 12, 67        |28, 09, 98              | 44, 84

99, 23        | 45           |12    | 67     |28, 09        | 98      |44     | 84

99   | 23   | 45           |12    | 67       |28    | 09   | 98      |44     | 84

Merge Phase

23, 99      | 45           |12, 67            |09, 28   | 98           | 44, 84

23, 45, 99                  | 12, 67          | 09, 28, 98              |   44, 84

12, 23, 45, 67, 99                            | 09, 28, 44, 84, 98

09, 12, 23, 28, 44, 45, 67, 84, 98, 99

Complexity Analysis

The Divide phase of merge sort will need log N operations as in every step we are reducing length of array by half.

Merge step will again have log N merges and in each merge step we will have maximum N comparison, so the overall complexity will (N log N)

# Factory Pattern

Factory Pattern is one of the highly used design patterns. The reason being , its genuine usefulness and closeness to real world. Let’s take a very simple real world example to get started, and then we will map it to the pattern.

Let’s say we have a Car factory which creates many types of cars. To keep it simple, let’s say it creates 2 type of cars- hatchback & sedan. These two type of cars will have many similar attributes like top speed, power steering etc. but there will be some features explicit to type of car (say a back seat AC or TV is available only for sedan cars). What will be a natural Object Oriented Design for this arrangement?

Class Car Extended by Class Sedan and Class HatchBack

If you know what type of car you need beforehand, we are good. But in case you need to create the car at runtime, say on user input, you will need some helper class which will create specific type of car at runtime. This class is our factory class.

Class CarFactory

{

Public static Car getCar(String carType){

If(carType.equals(“sedan”)) return new Sedan();

else return new HatchBack();

}

}

A better example in technical terms might be that your application supports multiple database types (say on test environment you use MySql whereas on production you have Oracle). A DataBaseConnectionFactory can help you get connection of specific type of database at runtime (say reading the database type value from some property file.

# Heapsort: Algorithm and Complexity

Heap sort is one of the most important and interesting algorithms. The implementation is base of many other sophisticated algorithms. We will focus on basics of heap sorting here. Infact, if you understand what a heap data structure is, heap sort is just application of some known simple operations on the heap.

Let’s relook at our heap

This is a max heap so let’s try to create an array in reverse sorted order (a min heap is good for sorted in lowest to highest format and vice versa).  Before moving forward, revisit the heap data structure and understand Insert and Delete operations, after that heap sort algorithm is a cake walk.

We know that max heap has a property that element at the top is highest. Using this property, we can create an algorithm like

1. Create max heap from the random array
2. Remove top element from heap and add to reverse sorted array
3. Heapify (restore heap property) the remaining heap elements
4. Repeat Step 2 till the heap is empty

Step 1 is nothing but inserting all elements of an array to heap. One Insert Key operation takes Log N operations so N elements will take N Log N

Step 2 is order of 1 as we are just removing the top element and adding to our array

Step 3 is nothing but Delete Node operation in heap, i.e.  take last leaf node and add as root, then compare with its child nodes and swap with largest. Repeat the process till heap property is maintained, i.e. child is greater than parent.  This is Log N operations for one heapify.

Step 4 is combination of 2 & 3, N times. Step 2 is constant order and hence can be ignored. This means we have N Step 3 order or N Log N.

Combining Step 1 and 4, we figure out order of heap sort complexity is of  N Log N order.

http://kamalmeet.com/2011/07/insertion-sorting/

# Java multiple Inheritance: Interfaces and Composition

Inheritance means a class extending other class. Multiple Inheritance means single class extending more than one class. Java does not support this kind of inheritance as one class can inherit only a single class.

Q. Why Java does not support multiple inheritance?

Consider a scenario, there are 2 classes

class A{

public void mymethod(){//some code

}

}

class B{

public void mymethod(){//some code

}

}

class C extends A,B{//illegal in Java

//which implementation of mymethod is imported ?

}

If java allow multiple inheritance, it will be tricky to handle above situation with multiple inheritance, hence Java does not allow it.

Q. How does Java implement Multiple inheritance?

Java does not provide direct implementation of multiple inheritance by extending more than one classes, but it provides you 2 alternatives.

1. Use of Interfaces: A Java class cannot extend more than one class, but it can implement any number of interfaces.

Class C implements A,B{ // this time A and B are interface

public void mymethod(){//interfaces did not provide implementation and hence no conflict

}

}

2. Composition: Other way to use properties of other classes is to use composition, that is have the object of other classes as part of current class.

Class C{//A and B are different classes

A objA=new A();

B objB=new B();

}

Best Approach: A mix of implementing interfaces, extending class and using composition, based on different requirements