Merge Sort

Merge Sort :

Merge Sort is a divide and conquer algorithm. It produces a stable sort, which means that the implementation preserves the input order of equal elements in the sorted list. It produces In-place sort output.

Worst Case : O(n log n)

Average Case : O(n log n)

Best Case : O(n log n)

ALGORITHM:

    1. Divide the unsorted list into n sub-lists, each containing 1 element (a list of 1 element is considered sorted) by splitting it two repeatedly
  1. Repeatedly merge 2 sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

e.g. For array, 22, 33, 3, 5, 2, 99, Merge sort process is as follows :

merge sort

C SOURCE CODE:

Leave a Reply

Your email address will not be published. Required fields are marked *