//Define the Pattern Interface and Handler Objects.

//Define the IStrategy interface to be used as the "blueprint" for the main application classes.
//This interface defines the Sort() method. The Sort() method represents the different sort functions that can be applied.
public interface IStrategy
{
void Sort(List<string> list);
}

//The QuickSortStrategy class (object) represents a sort pattern that implements a quick sort algorithm.
public class QuickSortStrategy : IStrategy
{
public void Sort(List<string> list)
{
list.Sort();
}
}

//The MergeSortStrategy class (object) represents a sort pattern that implements a merge sort algorithm.
public class MergeSortStrategy : IStrategy

public void Sort(List<string> list)
{
string[] dataArray = MergeSort(list.ToArray());
list.Clear();
list.AddRange(dataArray);
}

private string[] SplitArray(string[] data, int lower, int upper)
{
string[] sub = new string[upper - lower + 1];
for (int i = lower; i <= upper && i < data.Length; i++)
{
sub[i - lower] = data[i];
}

return sub;
}

private string[] MergeSort(string[] data)
{
if (data.Length == 1)
return data;

int middle = data.Length / 2;
string[] left = MergeSort(SplitArray(data, 0, middle - 1));
string[] right = MergeSort(SplitArray(data, middle, data.Length - 1));
string[] result = new string[data.Length];

int dPtr = 0;
int lPtr = 0;
int rPtr = 0;

while (dPtr < data.Length)
{
if (lPtr == left.Length)
{
result[dPtr] = right[rPtr];
rPtr++;
}
else if (rPtr == right.Length)
{
result[dPtr] = left[lPtr];
lPtr++;
}
else if (String.Compare(left[lPtr], right[rPtr]) < 0)
{
result[dPtr] = left[lPtr];
lPtr++;
}
else
{
result[dPtr] = right[rPtr];
rPtr++;
}

dPtr++;
}

return result;
}
}

//The ShellSortStrategy class (object) represents a sort pattern that implements a shell sort algorithm.
public class ShellSortStrategy : IStrategy
{
public void Sort(List<string> list)
{
string[] dataArray = ShellSort(list.ToArray());
list.Clear();
list.AddRange(dataArray);
}

private string[] ShellSort(string[] data)
{
int size = data.Length;
int increment = size;
while (increment >= 1)
{
increment /= 3;
if (increment < 1) increment = 1;
for (int i = 0; i < increment; i++)
{
int j = i + increment;
while (j <= (size - 1))
{
int k = j;
while (string.Compare(data[k - increment], data[k]) > 0)
{
string temp = data[k - increment];
data[k - increment] = data[k];
data[k] = temp;
k = k - increment;
if ((k - increment) < 0) break;
}

j += increment;
}
}

if (increment == 1) break;
}

return data;
}
}