Java

Sort-merge algorithm

⏱️ 10 min de lecture 👁️ 2246 vues
Merge sorting is a sort algorithm  which consists of concatenating two lists sorted into one. Its principle is based on the method deviser pour régner. The advantage of sort-to-merge is that the two lists are merged at the same time, so we can do an implementation with threads.

The algorithm is known for its efficiency in complexity (time and memory) and for sorting lists:
  • We cut the data into two equal parts.
  • We sort the data of each part (we split each part, the algorithm becomes recursive).
  • We merge the two parts.
We recursively currency the starting array into two subarrays until the array contains only one element. Once the elements are sorted independently of each other, from that point on, the backtracking starts and we're going to merge the subtables into one until you get the sorted starting board. The merge consists of successive comparisons.

Example

Suppose we want to sort the following table: [ 38, 27 ,43, 3, 9, 82, 10]

Sorting Fusion in Java

Algorithm


TriFusion ALGORITHM(T, left, right);
    T: table of values;
    left,right: integer;
    center: integer;
TOP   
    IF (left < right) THEN
          ← center (left + right) / 2;
          TriFusion (T, left, center);
          TriFusion (T, center + 1, right);
          MERGE(T, left, center, right);
    FSI
FIN.

Commentaires (0)

Connectez-vous pour commenter

Rejoignez la discussion et partagez vos connaissances avec la communauté

Se connecter Créer un compte

Chargement des commentaires...