Study Abroad Education Loan College News Placement Book Shops E - Books Engg-Admission Edu-Classifieds Students-Forum
Easy Studies

Home Implementation Of Merge Sort▼

## Implementation Of Merge Sort:

Sorting:

Sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order.

Sorting algorithm classification:

Computaional complexcity.

Memory utilization

Stability-Maintaining relative order of records with equal keys.

No.of comparisions

Methods applied like insertion,exchange, selection,merging etc.

Sorting is a process of linear ordering of list of objects

Sorting techniques are categoried into:

1. Internal sorting

2. External sorting

Internal sorting:

It takes the place in the main memory of a computer.

Eg: Bubble sort,Insertion sort,Shell sort,Quick sort,Heap Sort,etc

External sorting:

It takes the place in secondary memory of a computer,Since the number of objects to be stored is too large to fit in main memory.

Eg:Merge sort,Multiway Merge,Polyphase merge.

Merge sort:

The most common algorithm used in external sorting is the mergesort.

This algorithm follows divide and conquer startegy.

i) Dividing Phase.

The problem is divided into smaller problem and solved recursively.

ii) Conquering Phase.

The partitioned array is merged together recursively.

Merge sort is an O(n log n) comparison-based sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm. It was invented by Jhn von Neumann in 1945.

Analysis of the Merge sort:

1. Worest case performance O(n log n)
2. Best case performance O(n log n)
3. Average case performance O(n log n)

1. It has better cache performance

2. Merge Sort is a Stable sort

3. It is simpler to understand than heapsort

Limitation:

1. It need secondary storage device for the large amount of data.

2. It requires extra memeory space.

3.  A small list will take fewer steps to sort than a large list.

Algorithm steps:

• If the list is of length 0 or 1, then it is already sorted. Otherwise:
• Divide the unsorted list into two sublists of about half the size.
• Sort each sublist recursively by re-applying merge sort.
• Merge the two sublists back into one sorted list.
C Program To Implement Merge Sort

CPP Program To Implement Merge Sort