विलीनीकरण क्रम अल्गोरिदम एक विभाजन-संपादन अल्गोरिदम आहे. स्प्लिट-अचीव्हमेंट पॅराडाइममध्ये, समस्या लहान समस्यांमध्ये विभागली गेली आहे, जिथे प्रत्येक लहान समस्या अजूनही मोठ्या आकाराचे सर्व गुणधर्म त्याच्या आकाराशिवाय वगळते. सुरुवातीच्या समस्येचे निराकरण करण्यासाठी, प्रत्येक तुकडा स्वतंत्रपणे सोडवला जातो; नंतर तुकडे पुन्हा एकत्र केले जातात. उदाहरणार्थ, कल्पना करा की आपल्याला बबल सॉर्ट अल्गोरिदम वापरून 200 घटकांची अॅरे क्रमवारी लावण्याची आवश्यकता आहे. कारण वर्गीकरण पर्याय देते (N ^ 2) वस्तुमान क्रमवारी लावण्यासाठी सुमारे 40,000 तास लागतील. आता अॅरेला दहा समान भागांमध्ये विभाजित करण्याची कल्पना करा, प्रत्येक तुकडा वर्गीकरण करून स्वतंत्रपणे व्यवस्थित करा. आता प्रत्येक तुकडा क्रमवारी लावण्यासाठी 400 वेळा लागतील; सामान्यतः 10 * 400 = 4000:.

प्रत्येक तुकडा क्रमवारी लावल्यावर, त्यांना पुन्हा एकत्र केल्याने सुमारे 200 युनिट मिळतील; 200 + 4000 = 4,200 एकूण. हे स्पष्ट आहे की 4,200 एक प्रभावी सुधारणा आहे – 40,000 पेक्षा जास्त.

आता मोठा विचार करा. प्रारंभिक वस्तुमान दोन गटांमध्ये विभागण्याची आणि नंतर त्यांची क्रमवारी लावण्याची कल्पना करा. अखेरीस, अॅरेची क्रमवारी लावण्यासाठी सुमारे 1,000 युनिट्स लागतील.

अशा प्रकारे विलीनीकरण वर्गीकरण कार्य करते. यामुळे मोठ्या अॅरेची क्रमवारी लावणे सोपे होते, म्हणून ते मोठ्या संख्येने आणि ओळींच्या अॅरेसाठी योग्य आहे. विलीनीकरण अल्गोरिदमची वेळ जटिलता सर्वोत्तम, सरासरी worst सर्वात वाईट և समान आहे हे ओ (एन * लॉग (एन)) च्या समान आहे

बीटीडब्ल्यू, जर तुम्ही अल्गोरिदम և डेटा स्ट्रक्चर basic मूलभूत वर्गीकरणापासून अपरिचित և स्पीड, बायनरी सर्च, लेव्हल ऑर्डर सर्च և इत्यादी अल्गोरिदम शोधत असाल तर मी तुम्हाला एक चांगला, सर्वसमावेशक ऑनलाइन कोर्स घेण्याची सूचना देतो डेटा स्ट्रक्चर्स – अल्गोरिदम. जावा वापरून डीप डायव्ह: प्रथम मूलभूत गोष्टी शिका.

मर्ज सॉर्ट अल्गोरिदम वापरून जावामध्ये जावा फायलींची क्रमवारी लावणे

आपण पूर्णांकांची अनियमित यादी दिली आहे (किंवा इतर कोणतीही वस्तू, जसे की तार), आपल्याला संपूर्ण संख्या किंवा वस्तू त्यांच्या नैसर्गिक क्रमाने पुन्हा व्यवस्थित करणे आवश्यक आहे.

नमुना इनपुट: {80, 50, 30, 10, 90, 60, 0, 70, 40, 20, 5}
नमुना आउटपुट: {0, 10, 20, 30, 40, 50, 50, 60, 70, 80, 90}

import java.util.Arrays;

/*
 * Java Program to sort an integer array using merge sort algorithm.
 */

public class Main {

  public static void main(String[] args) {

    System.out.println("mergesort");
    int[] input = { 87, 57, 370, 110, 90, 610, 02, 710, 140, 203, 150 };

    System.out.println("array before sorting");
    System.out.println(Arrays.toString(input));

    // sorting array using MergeSort algorithm
    mergesort(input);

    System.out.println("array after sorting using mergesort algorithm");
    System.out.println(Arrays.toString(input));

  }

  /**
   * Java function to sort given array using merge sort algorithm
   * 
   * @param input
   */
  public static void mergesort(int[] input) {
    mergesort(input, 0, input.length - 1);
  }

  /**
   * A Java method to implement MergeSort algorithm using recursion
   * 
   * @param input
   *          , integer array to be sorted
   * @param start
   *          index of first element in array
   * @param end
   *          index of last element in array
   */
  private static void mergesort(int[] input, int start, int end) {

    // break problem into smaller structurally identical problems
    int mid = (start + end) / 2;
    if (start < end) {
      mergesort(input, start, mid);
      mergesort(input, mid + 1, end);
    }

    // merge solved pieces to get solution to original problem
    int i = 0, first = start, last = mid + 1;
    int[] tmp = new int[end - start + 1];

    while (first <= mid && last <= end) {
      tmp[i++] = input[first] < input[last] ? input[first++] : input[last++];
    }
    while (first <= mid) {
      tmp[i++] = input[first++];
    }
    while (last <= end) {
      tmp[i++] = input[last++];
    }
    i = 0;
    while (start <= end) {
      input[start++] = tmp[i++];
    }
  }
}

Output
mergesort
array before sorting
[87, 57, 370, 110, 90, 610, 2, 710, 140, 203, 150]
array after sorting using mergesort algorithm
[2, 57, 87, 90, 110, 140, 150, 203, 370, 610, 710]

आपण पाहू शकता की अॅरे आता क्रमवारी लावली आहे. आम्ही वापरत असलेले अल्गोरिदम म्हणजे विलीनीकरण क्रमवारीची पुनरावृत्ती अंमलबजावणी և ते स्थिर वर्गीकरण अल्गोरिदम मला म्हणायचे आहे, ते टायच्या बाबतीत घटकांचा मूळ क्रम राखते.

कोणत्याही परिस्थितीत, विलीनीकरण क्रमवारी अल्गोरिदम कसे कार्य करते हे आपल्याला अद्याप समजले नसल्यास, आपण हे देखील तपासू शकता अल्गोरिदम և डेटा स्ट्रक्चर्स – भाग 1 2: Pluralsight कोर्स जो की वर्गीकरण स्पष्ट करतो al अल्गोरिदम शोधणे खूप छान पद्धतीने. यात मूलभूत डेटा स्ट्रक्चर्सचा समावेश आहे जसे की लिंक केलेली यादी, अॅरे, हॅश टेबल, बायनरी ट्री इ.

एवढे जावा मध्ये मर्ज सॉर्ट अल्गोरिदम कसे लागू करावे. क्विकसॉर्टसह, हे एक शक्तिशाली वर्गीकरण अल्गोरिदम आहे जे वास्तविक-जगातील, सामान्य-हेतू ग्रंथालयांमध्ये वापरले जाते. खरं तर, जावा Collections.sort () आणि Arrays.sort () वस्तूंना नुकसान करण्यासाठी पद्धतीमध्ये फ्यूजन प्रकार देखील वापरला जातो.

जर तुम्ही एखाद्या प्रोग्रामिंग जॉब मुलाखतीची तयारी करत असाल, तर तुम्हाला ते कसे करावे हे माहित असणे आवश्यक आहे – वेळेची गुंतागुंत शोधा – जागा. आपण विनंती केल्यास, विलीनीकरण क्रमवारीच्या “गती” मधील फरक स्पष्ट करण्यास सक्षम असावे.

येथे लक्षात ठेवण्याची मुख्य गोष्ट अशी आहे की जरी दोन्ही क्रमाने विलीन होतात जलद वर्गीकरण केसची मध्यम वेळ जटिलता आहे Օ (NlogN), फ्यूजन सॉर्टिंगपेक्षा क्विकॉर्ट चांगले आहे कारण क्विकॉर्ट कॉन्स्टंट फ्यूजन सॉर्टिंगपेक्षा लहान आहे.

खरं तर, Օ (NlogN) आहे: K * O (nLogN), बिग ओ मार्क या स्थिरांकाकडे दुर्लक्ष करतो कारण जेव्हा इनपुटचा आकार भौमितिकदृष्ट्या वाढतो तेव्हा ते अशक्य होते, परंतु त्याच वेळी जटिल अल्गोरिदमच्या बाबतीत हा स्थिरांक एक वेगळा घटक असू शकतो, कारण हा हाय-स्पीड फ्यूजनच्या बाबतीत आहे.

हे देखील लक्षात ठेवले पाहिजे की हे पुनरावृत्ती अल्गोरिदम आहे जे पुनरावृत्तीद्वारे सहजपणे लागू केले जाऊ शकते.