# Back to basics – Part 1..of..n-1 – Algorithm to Merge Sorted Sequences using C#

This is another episode of the “so called my **sporadic**” series, mentioned long long time ago. This time we’ll be discussing the biggest merger ever in the United States History, __Merger of two Sorted Sequences__ :) like arrays, lists etc. I’ll try to go from more concrete to generic one, like taking **‘int’** sequences as concrete type and end up with generic<t> that caters all types. [digg]

The algorithm is pretty simple, take a look by yourself:

Lets say we have two __sorted__ **‘int’** arrays, shown below:

Here i & j represents pointers/indices to __Left__ and __Right__ arrays respectively and initially are at 0. Next we check that Left[i] >= Right[j], if yes we’ll take the right one and increment the **i** (i++), else if Left[i] < Right[i], we’ll take the left item and increment **j **(j++). Until we reach to a point where one of the sequence is processed fully and there are some elements left in the other array. That is in our case, Left one will be processed earlier and there still have some elements left in the right array. This is what is called the **skip-state **that is pointed by **‘k’** index/pointer**,** where we take the rest of the elements from the right array and place them in the temporary array/container merged_array. The skip state is shown below with **k** pointer/index:

Here is the flow chart for the algorithm.

Now lets go into the implementation of it. I have implemented the algorithm in four ways:

- Concrete implementation, for
**ints**without the*Extension methods*(**greedy**approach). - Concrete implementation, for
**ints**, using*Extension methods*(**greedy**approach). - Generic implementation using
*Extension methods*,**greedy**approach. - Generic implementation using
*Extension methods*,**lazy**approach (using**yields**).

Let’s take the top down approach and start with the usage of the above mentioned implementations. Take a closer look @ (1), (2), (3) & (4).

static void Main(string[] args)

{

int[] left_array = { 1, 3, 5, 7, 40 };

int[] right_array = { 4, 6, 30, 30, 40, 50 };var results = MergeSortedArrays(left_array, right_array); // (1)

var results2 = left_array.MergeSortedArrays(right_array); // (2)

// using generics, greedy approach.

var results3 = left_array.MergeSortedSequences(right_array, (a1, a2) => (a1 >= a2) ); // (3)

// this one calls the Lazy one, with yield.

var result4 = left_array

.MergeSorted(right_array, (a1, a2) => (a1 >= a2))

.ToArray(); // (4)

}

1) Here is the Concrete implementation of the first one, for **int **types without the *Extension methods* (**greedy** approach).

public static int[] MergeSortedArrays(int[] left_array, int[] right_array)

{

// bounds checking.

if (left_array == null ||

right_array == null ||

left_array.Count() == 0 ||

right_array.Count() == 0)

return null;// created an array to hold the results

int count = left_array.Count() + right_array.Count();

int[] merged_array = new int[count];// temp array points to the array that has to be processed during

// skip state

int[] temp_array = null;// at start the skip state is false, no skipping of data.

bool skip_state = false;// i and j are pointers for both the arrays, while k is the pointer where skip

// of data has to begin i.e. skipstate

int i = 0;

int j = 0;

int k = 0;// initially the counter is zero, and

// represents start of the traversal

int counter = 0;// lets begon the traversal.

while (counter < count)

{

if (left_array[i] < right_array[j])

{

merged_array[counter++] = left_array[i++];if (i == left_array.Count()) { skip_state = true; temp_array = right_array; k = j; }

}

else

{

merged_array[counter++] = right_array[j++];if (j == right_array.Count()) { skip_state = true; ; temp_array = left_array; k = i; }

}// At skip state traverse the rest.

if (skip_state)

{

while (counter < count)

{

merged_array[counter++] = temp_array[k++];

}

}

}return merged_array;

}

2) Do we need the second while loop, I don’t think so, sounds redundant. Refined it, this one is with the Extension methods, and the arguments are now of type IEnumerable<>, instead of arrays[], we are getting close to generic solutions, correct! Since all collections implements IEnumerable<>, after little refactoring, it is now **LINQ-able **(that requires composable or **fluent** API which is based on chain of responsibility pattern). I’ll discuss this in more details, in coming sessions, on **LINQ**, that why we need **IEnumerable<T>** and **IQueryable<T>** etc. This one also is a greedy approach.

public static IEnumerable<int> MergeSortedArrays(this IEnumerable<int> left,

IEnumerable<int> right)

{

// bounds checking, we can consider throwing exception as well.

if (left == null ||

right == null ||

left.Count() == 0 ||

right.Count() == 0) return null;// created an array to hold the results

int count = left.Count() + right.Count();

int[] merged_array = new int[count];// temp array points to the array that has to be processed during

// skip state

IEnumerable<int> temp_array = null;// at start the skip state is false, no skipping of data.

bool skip_state = false;// i and j are pointers for both the arrays, while k is the pointer where skip

// of data has to begin i.e. skipstate

int i = 0;

int j = 0;

int k = 0;// initially the counter is zero, and

// represents start of the traversal

int counter = 0;// lets begon the traversal.

while (counter < count)

{

// At skip_state traverse the rest and loop back.

if (skip_state)

{

merged_array[counter++] = temp_array.ElementAt(k++);

}

else if (left.ElementAt(i) >= right.ElementAt(j))

{

merged_array[counter++] = right.ElementAt(j++);if (j == right.Count()) { skip_state = true; ; temp_array = left; k = i; }

}

else

{

merged_array[counter++] = left.ElementAt(i++);if (i == left.Count()) { skip_state = true; temp_array = right; k = j; }

}

}return merged_array;

}

So all we need is the introduction of another **‘ if ‘** statement and no need of another nested while loop (always avoid redundancy). Seems like we are getting the *Algorithm’s Complexity* of **O(n),** very nice.

3) The generic approach, with extension method. Also, introducing, the comparer, a **callback, **or delegate of type * Func<T,T,bool>,* greedy as well:

public static IEnumerable<T> MergeSortedSequences<T>(this IEnumerable<T> left,

IEnumerable<T> right,

Func<T, T, bool> Comparer)

{

// bounds checking, we can consider throwing exception as well.

if (left == null ||

right == null ||

left.Count() == 0 ||

right.Count() == 0) return null;// created an array/list to hold the results

int count = left.Count() + right.Count();

List<T> merged_array = new List<T>(count);// temp array points to the array that has to be processed during

// skip state

IEnumerable<T> temp_array = null;// at start the skip state is false, no skipping of data.

bool skip_state = false;// i and j are pointers for both the arrays, while k is the pointer where skip

// of data has to begin i.e. skipstate

int i = 0;

int j = 0;

int k = 0;// initially the counter is zero, and

// represents start of the traversal

int counter = 0;// lets begon the traversal.

while (counter < count)

{

// At skip_state traverse the rest and loop back.

if (skip_state)

{

counter++;

merged_array.Add(temp_array.ElementAt(k++));

}

else // first >= second, take second.

if (Comparer(left.ElementAt(i), right.ElementAt(j)))

{

counter++;

merged_array.Add(right.ElementAt(j++));if (j == right.Count()) { skip_state = true; ; temp_array = left; k = i; }

}

else // first < second, take first.

{

counter++;

merged_array.Add(left.ElementAt(i++));if (i == left.Count()) { skip_state = true; temp_array = right; k = j; }

}

}return merged_array;

}

4) Here comes the final one, my favorite, using * Extension method, Generic and Lazy (or Deferred Execution),* I am using

**yield**and the good part is no intermediary container is required in this case, as we saw in the previous implementations. This is now fully

**LINQ**ready, and we can apply as many LINQ operations, as needed.

/// <summary>

/// Merges the sorted sequence using yields(lazy),

/// no temporary container required in this version.

/// </summary>

/// <typeparam name="T"></typeparam>

/// <param name="left">The first/left sequence.</param>

/// <param name="right">The second/right sequence.</param>

/// <param name="Comparer">The comparer.</param>

/// <returns>IEnumerable<T></returns>

public static IEnumerable<T> MergeSorted<T>(this IEnumerable<T> left,

IEnumerable<T> right,

Func<T, T, bool> Comparer)

{

// nulls/bounds checking.

if (left == null ||

right == null ||

left.Count() == 0 ||

right.Count() == 0)

{

yield break; // no need to proceed.

}// created an array/list to hold the results

int count = left.Count() + right.Count();// temporary container not required, in the 'yield' scenario, so commented out.

//List<T> merged_array = new List<T>(count);// temp array points to the array that has to be processed during

// skip state

IEnumerable<T> temp_array = null;// at start the skip state is false, no skipping of data.

bool skip_state = false;

// of data has to begin i.e. skipstate

int i = 0;

int j = 0;

int k = 0;// initially the counter is zero, and

// represents start of the traversal

int counter = 0;// lets begon the traversal.

while (counter < count)

{

// At skip_state traverse the rest and loop back.

if (skip_state)

{

counter++;

yield return temp_array.ElementAt(k++);

}

else // first >= second, take second.

if (Comparer(left.ElementAt(i), right.ElementAt(j)))

{

counter++;

yield return right.ElementAt(j++);if (j == right.Count()) { skip_state = true; ; temp_array = left; k = i; }

}

else // first < second, take first.

{

counter++;

yield return left.ElementAt(i++);if (i == left.Count()) { skip_state = true; temp_array = right; k = j; }

}

}

}

The code is self explanatory. Although this is a simple algorithm, but main idea was to present it in different ways so the viewers will get different flavors of implementing it in .NET using C#.

That's all for now folks, I hope it was helpful. I appreciate you please leave your valuable feedback. Enjoy!

If you enjoyed reading this blog, leave your valuable

and consider subscribing to the RSS feed. You can also subscribe to it by email. Also, you can follow me on Twitter. Thank you!feedback

### Comments (4) -

### Add comment

12/8/2017 2:50:18 AM #

I really like gathering useful information, this post has got me even more info! Review my blog post - auto part drop shipping; lyonskaufman8.jiliblog.com - lyonskaufman8.jiliblog.com/.../find-best-deals-for-top-quality-truck-parts ,

12/8/2017 3:30:32 AM #

11:54 am: Coming to everyone else in the fall.

12/8/2017 6:44:52 AM #

11:27 am: 4,000 brand-new creator APIs.

12/8/2017 9:56:20 AM #

“Philadelphia: Fri and Saturday, September 25-26” and since my iPhone would arrive through Philly

12/8/2017 7:15:29 PM #

I am sure this piece of writing has touched all the internet people, its really really pleasant post on building up new website. My website ... junk Yards - clemmensen91bridges.fitnell.com/.../custom-wheels-for-your-car

12/9/2017 1:21:23 AM #

Built for connecting Thunderbolt hard drives and monitors to Macs using a single type of cable, Apple and Intel’s jointly-developed Thunderbolt and Thunderbolt 2 standards guarantee up to 10Gbps (gigabit per second) and 20Gbps speeds, respectively.

12/9/2017 7:20:49 AM #

I'm truly enjoying the design and layout of your website. It's a very easy on the eyes which makes it much more pleasant for me to come here and visit more often. Did you hire out a developer to create your theme? Excellent work! My website - running engine - www.chictopia.com - http://www.chictopia.com/clemmensen97hanley ,

12/10/2017 6:18:51 PM #

Just wish to say your article is as astounding. The clarity in your post is simply cool and i can assume you're an expert on this subject. Fine with your permission let me to grab your RSS feed to keep up to date with forthcoming post. Thanks a million and please continue the rewarding work.

12/11/2017 11:49:09 AM #

Sommige vrouwen houden ervan om actief te vrijen met hun vriendin, anderen laten zich liever verleiden.

12/11/2017 2:51:57 PM #

Hey there! I could have sworn I've been to this site before but after browsing through some of the post I realized it's new to me. Anyways, I'm definitely happy I found it and I'll be book-marking and checking back frequently! Stop by my blog - clinamax - https://clinamaxpills.com/

12/16/2017 1:00:00 AM #

Teu marujo parece nunca nos acreditar! Art.

12/16/2017 7:13:35 PM #

Here is my blog post: in vitro fertilization twins - www.nationalgasco.net/.../Default.aspx