# Merge Sort

> A method of merging multiple sorted data sets into one sorted set

<br>

*Most efficient method for linked lists!*

<br>

### Utilizing Divide and Conquer Algorithm

* Divide data into minimum unit problems, then sort in order to get final results
  * `top-down` approach

<br>

### Time Complexity

* O(n log n)

<br>

### Merge Sort Process

1. Divide Phase
   * Continue dividing the entire data set until it becomes minimum-sized subsets
2. Merge Phase
   * Sort and merge two subsets into one set

<br>

### Divide Process Algorithm

```python
def merge_sort(m):
    if len(m) <= 1: # Return immediately if size is 0 or 1
        return m
    
    # 1. Divide part
    mid = len(m)//2
    left = m[:mid]
    right = m[mid:]
    
    # Recursively call merge_sort until list size becomes 1
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 2. Conquer part: Merge divided lists
    return merge(left, right)
```

<br>

### Merge Process Algorithm

```python
def merge(left, right):
    result = [] # Merge two divided lists to create result
    
    while len(left) > 0 and len(right) >0: # When elements remain in both lists
        # Compare first elements of two sub lists and add smaller ones to result first
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if len(left) > 0: # When elements remain in left list
        result.extend(left)
    if len(right) > 0: # When elements remain in right list
        result.extend(right)
    return result
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chloe-codes1.gitbook.io/til/algorithm/sorting-methods/merge_sort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.