# What Is a Merge Sort in Data Structure?

//

Heather Bennett

A merge sort is a popular sorting algorithm used in data structures. It is known for its efficiency and ability to handle large amounts of data. In this article, we will explore what a merge sort is, how it works, and why it is advantageous.

## What is a Merge Sort?

A merge sort is a divide-and-conquer algorithm that divides an unsorted list into smaller sublists, sorts them individually, and then merges them back together to create the final sorted list. It follows the principle of recursion to solve the problem at hand.

## How Does Merge Sort Work?

The merge sort algorithm can be summarized in three basic steps:

1. Divide: The unsorted list is divided into two equal halves until each sublist contains only one element. This process continues until we reach the base case of having one-element sublists.
2. Conquer: The one-element sublists are considered sorted by default.

Then, the merging process begins by comparing elements from each sublist and merging them in a sorted order. This step continues until all sublists are merged back into a single sorted list.

3. Merge: The merging process involves comparing elements from two sublists and putting them in the correct order in the resulting merged sublist. This step repeats until there are no more elements left to compare and merge.

### Example:

To illustrate how merge sort works, let’s take an example of an unsorted list: [7, 2, 5, 1, 8, 3].

Step 1: Divide

• [7, 2, 5] | [1, 8, 3]

Step 2: Conquer & Merge

• [7] | [2] | [5]
• [1] | [8] | [3]

Step 3: Merge

• [2, 7] | [1, 3, 8]

Step 4: Merge (Final)

• [1, 2, 3, 5, 7, 8]