Header Ads Widget

Responsive Advertisement

Merge Sort simple under standing

Kartik Chandra Mandal June 22, 2016


The Merge Sort algorithm in Java, which is a divide-and-conquer sorting algorithm with a time complexity of O(nlogn). Below is a breakdown of the key components of the code:

Java

public class Mergesort {
 public static void merge(int[] list, int start, int middle, int end)
 {
  int[] tmp = new int[list.length];
  int ai = start, bi = middle, ti = start;

  while (ai < middle || bi < end)
  {
   if (ai == middle)   tmp[ti++] = list[bi++];
   else if (bi == end)          tmp[ti++] = list[ai++];
   else if (list[ai] < list[bi])         tmp[ti++] = list[ai++];
   else                    tmp[ti++] = list[bi++];
  }

  for (ti = start; ti < end; ti++)
   list[ti] = tmp[ti];
 }

 public static void mergesort(int[] lst, int start, int end)
 {
  if (end-start < 2)
   return;
 
  mergesort(lst, start, start + (end-start) / 2);
  mergesort(lst, start + (end-start) / 2, end);
  merge(lst, start, start + (end-start) / 2, end);
 }
 public static void main(String[] args)
 {
  int[] lst = new int[] {10, 9, 8, 4, 5, 6, 7, 3, 2, 1};

  mergesort(lst, 0, lst.length);
  for (int i = 0; i < lst.length; i++)
   System.out.print(lst[i] + " ");
  System.out.println("\n");
 }

}

 

1. merge Method:

This method merges two sorted subarrays of the main array (list). It takes three parameters:

Ø  start: Starting index of the first subarray.

Ø  middle: Starting index of the second subarray (also the ending index of the first subarray).

Ø  end: Ending index of the second subarray.

The method works as follows:

Ø  Two pointers ai (for the first subarray) and bi (for the second subarray) are initialized. The elements from both subarrays are compared, and the smaller of the two is placed into the temporary array tmp.

Ø  After merging both subarrays, the result is copied back to the original list from the temporary array.

2. mergesort Method:

This is the recursive method that implements the divide step of the Merge Sort algorithm:

Ø  If the length of the subarray is less than 2 (i.e., it has only one element), it is already sorted, so the method returns.

Ø  Otherwise, the method splits the array into two halves by recursively calling itself on each half (lst[start, middle] and lst[middle, end]).

Ø  Once the halves are sorted, the merge function is called to merge the two sorted subarrays.

3. main Method:

This method provides a simple example of using the mergesort algorithm:

Ø  It initializes an unsorted array lst.

Ø  It calls mergesort on the entire array.

Ø  Finally, it prints the sorted array to the console.

Example Output:

For the input array {10, 9, 8, 4, 5, 6, 7, 3, 2, 1}, the program will output:

1 2 3 4 5 6 7 8 9 10

 

How Merge Sort Works:

Ø  The array is recursively split into two halves until each subarray contains one element.

Ø  The merge step combines the sorted subarrays into a larger sorted array.

For example:

  1. Split {10, 9, 8, 4, 5, 6, 7, 3, 2, 1} into {10, 9, 8, 4, 5} and {6, 7, 3, 2, 1}.
  2. Further split them into smaller subarrays until single elements are obtained.
  3. Merge the subarrays back together, ensuring the elements are in order.

Merge Sort simple under standing
Merge Sort simple under standing


 

Merge Sort Visualization

Tags:

Post a Comment

0 Comments

Post a Comment