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:
Stability-Maintaining relative order of records with equal keys.
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
It takes the place in the main memory of a computer.
Eg: Bubble sort,Insertion sort,Shell sort,Quick sort,Heap Sort,etc
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.
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:
- Worest case performance O(n log n)
- Best case performance O(n log n)
- 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
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.
C Program To Implement Merge Sort
- 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.
CPP Program To Implement Merge Sort