To iterate is human, to recurse divine. L. Peter Deutsch
Merge sort is a divide and conquers and comparison-based sorting algorithm. It divide the array into subarray and conquer recursively sorting two subarrays. It combines the results into a final array.
Divide the problem into small subproblems.
Solve the subproblem using recursive function.
Combine the sub solution into solution.
Merge sort can be implemented Top-down and Bottom-up. Top down merge sort split the list into sub list and sort the sub list. Finally, it merges sorted sublist into a single sorted list. Bottom up merge sort treats array of sub list and iteratively merges sub-lists back and forth between two buffers.
Merge sort uses for linked list sorting, external sorting on the tab. It is stable sort compare then other sorting algorithm.
Write a program to take the un-sorted array and sort the array using Merge sort.
Unsorted array before sorting: [12, 11, 13, 5, 6, 7] Sorted array After Merge sort sorting: [5, 6, 7, 11, 12, 13]