Book Image

Everyday data structures

By : William Smith
Book Image

Everyday data structures

By: William Smith

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
Table of Contents (20 chapters)
Everyday Data Structures
Credits
About the Author
About the Reviewer
www.PacktPub.com
Customer Feedback
Preface
Free Chapter
1
Data Types: Foundational Structures

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) 
      { 
     ...