#### Overview of this book

Explore a new world of data structures and their applications easily with this data structures book. Written by software expert William Smith, you?ll learn how to master basic and advanced data structure concepts. ? Fully understand data structures using Java, C and other common languages ? Work through practical examples and learn real-world applications ? Get to grips with data structure problem solving using case studies
Everyday Data Structures
Credits
www.PacktPub.com
Customer Feedback
Preface
Free Chapter
Data Types: Foundational Structures
Arrays: Foundational Collections
Lists: Linear Collections
Stacks: LIFO Collections
Queues: FIFO Collections
Dictionaries: Keyed Collections
Sets: No Duplicates
Structs: Complex Types
Trees: Non-Linear Structures
Heaps: Ordered Trees
Graphs: Values with Relationships
Sorting: Bringing Order Out Of Chaos
Searching: Finding What You Need

## Merge sort

Merge sort is another popular version of the divide and conquer algorithm. It is a very efficient, general-purpose sort algorithm. The algorithm gets is named from the fact that it divides the collection in half, recursively sorts each half, and then merges the two sorted halves back together. Each half of the collection is repeatedly halved until there is only one object in the half, at which point it is sorted by definition. As each sorted half is merged, the algorithm compares the objects to determine where to place each sub set.

As far as divide and conquer algorithms are concerned, merge sort is one of the most efficient algorithms. The algorithm has a worst-, average- and best- case complexity of O(n log(n)), making it an improvement over quick sort even in the worst circumstances.

C#

```    public void MergeSort(int[] values, int left, int right)
{
if (left == right)
return;

if (left < right)
{
...```