# Merge Sort in Data Structures - Infovistar

### Merge Sort

Merge sort is the sorting algorithm that follows the divide and conquer technique. It is a popular and efficient sorting algorithm.

It splits the given list into two equal list i.e. sub-list. calls itself for the two lists and then merges the two sorted list.

The process of splitting and merging can be carried out recursively till there is only element in the list.

An array with single element is alway sorted.

### Time Complexity

Case Time Complexity
Best Case O(n log n)
Average Case O(n log n)
Worst Case O(n log n)
• Best Case O(n log n):It occurs when there is no sorting needed, i.e. the array is already sorted.
• Average Case O(n log n): The array elements are in a jumbled order that is not properly ascending and descending.
• Worst Case O(n log n): This occurs when the array elements need to be sorted in reverse order.

### Space Complexity

 Space Complexity O(n) Stable Yes
• A merge sort required extra variables for swapping. Hence, the space complexity of merge sorting is `O(n)`.
{"ft_lang_label":"__label__en","ft_lang_prob":0.54779196,"math_prob":0.8735462,"size":3972,"snap":"2023-40-2023-50","text_gpt3_token_len":1238,"char_repetition_ratio":0.124747984,"word_repetition_ratio":0.52895755,"special_character_ratio":0.38217524,"punctuation_ratio":0.19384265,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.990735,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-01T13:06:52Z\",\"WARC-Record-ID\":\"<urn:uuid:74b21e1d-b980-4157-ac0e-80223c74dd1e>\",\"Content-Length\":\"38938\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:e83cbe55-c434-4eb9-9cf0-6cbb66805485>\",\"WARC-Concurrent-To\":\"<urn:uuid:aedc19f4-7e92-4b96-8286-725155d9da9f>\",\"WARC-IP-Address\":\"103.117.212.77\",\"WARC-Target-URI\":\"https://infovistar.com/data-structures/sorting/merge-sort\",\"WARC-Payload-Digest\":\"sha1:36EWOKSEKIFVWENSBWR7LT2PZIJODCHI\",\"WARC-Block-Digest\":\"sha1:KU5AZPJF22UGAYI6BJKU26JANQ3L4WI7\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100287.49_warc_CC-MAIN-20231201120231-20231201150231-00683.warc.gz\"}"}